Partial Bi-immunity, Scaled Dimension, and NP-Completeness

No abstract is available for this paper.

• Publication year

  2008

• Venue

  Theory of Computing Systems

• Publication date

  2008-01-02

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00224-007-9000-2
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Mathematical Systems Theory I

  2006cited by this paper
• Hardness Hypotheses, Derandomization, and Circuit Complexity

  2004cited by this paper
• Small spans in scaled dimension

  2003cited by this paper
• Scaled dimension and nonuniform complexity

  2003cited by this paper
• MAX3SAT is exponentially hard to approximate if NP has positive dimension

  2002cited by this paper
• Bi-immunity separates strong NP-completeness notions

  2002cited by this paper
• Dimension in complexity classes

  2000cited by this paper
• Complexity theory retrospective II

  1998cited by this paper
• Structural properties of complete problems for exponential time

  1998cited by this paper
• Separating NP-completeness notions under strong hypotheses

  1997cited by this paper
• Cook Versus Karp-Levin: Separating Completeness Notions if NP is not Small

  1996influential reference
• On the structure of complete sets

  1994cited by this paper
• On A-Truth-Table-Hard Languages

  1993cited by this paper
• Completeness for nondeterministic complexity classes

  1991cited by this paper
• On polynomial time bounded truth-table reducibility of NP sets to sparse sets

  1990cited by this paper
• Structural properties of nondeterministic complete sets

  1990cited by this paper
• Cook Reducibility is Faster than Karp Reduciblity in NP

  1990cited by this paper
• Complexity Measures for Public-Key Cryptosystems

  1988influential reference
• A Comparison of Polynomial Time Completeness Notions

  1987cited by this paper
• Bi-immune sets for complexity classes

  1985cited by this paper
• Reductions on NP and P-Selective Sets

  1982influential reference
• Completeness, Approximation and Density

  1981cited by this paper
• A Comparison of Polynomial Time Reducibilities

  1975influential reference
• Complexity of Computer Computations

  1972cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper
• The complexity of theorem-proving procedures

  1971cited by this paper
• Cook Reducibility Is Faster than Karp Reducibility in

  year unknowncited by this paper

• Randomness in completeness and space-bounded computations

  2015cites this paper
• Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis

  2014cites this paper
• Scaled Dimension and the Berman-Hartmanis Conjecture

  2011cites this paper
• Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses

  2010cites this paper
• Comparing reductions to NP-complete sets

  2006cites this paper
• Two Open Problems on Effective Dimension

  2006cites this paper
• Pushdown dimension

  2005cites this paper
• SIGACT news complexity theory column 48

  2005influential citation
• Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets

  2004cites this paper
• Hardness Hypotheses, Derandomization, and Circuit Complexity

  2004cites this paper