$$P\mathop{ =}\limits^{?}NP$$
From MaRDI portal
Publication:2826803
DOI10.1007/978-3-319-32162-2_1zbMath1358.68106OpenAlexW2486916127MaRDI QIDQ2826803
Publication date: 18 October 2016
Published in: Open Problems in Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-32162-2_1
NP-completenessdiagonalizationinteractive proofsBoolean circuitsgeometric complexity theoryP versus NParithmetic circuit complexity
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Cites Work
- Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient
- Arithmetic circuits: the chasm at depth four gets wider
- The complexity of computing the permanent
- BPP and the polynomial hierarchy
- Relativized circuit complexity
- The intractability of resolution
- The monotone circuit complexity of Boolean functions
- The method of forced enumeration for nondeterministic automata
- A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
- Does co-NP have short interactive proofs ?
- Are there interactive protocols for co-NP languages?
- Probabilistic algorithm for testing primality
- Some results on relativized deterministic and nondeterministic time hierarchies
- Average case complexity under the universal distribution equals worst- case complexity
- The gap between monotone and non-monotone circuit complexity is exponential
- Modular elliptic curves and Fermat's Last Theorem
- Oracles and queries that are sufficient for exact learning
- Cook's versus Valiant's hypothesis
- Gaussian elimination is not optimal
- Relationships between nondeterministic and deterministic tape complexities
- Fast Parallel Computation of Polynomials Using Few Processors
- Arithmetic Circuits: A survey of recent results and open questions
- Irregular Primes and Cyclotomic Invariants to Four Million
- A Dynamic Programming Approach to Sequencing Problems
- Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
- Approximate Solutions for the Bilinear Form Computational Problem
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Rapid Multiplication of Rectangular Matrices
- Accessible Independence Results for Peano Arithmetic
- Every Prime Has a Succinct Certificate
- On the Structure of Polynomial Time Reducibility
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- A Fast Monte-Carlo Test for Primality
- The honeycomb model of $GL_n(\mathbb C)$ tensor products I: Proof of the saturation conjecture
- A Pseudorandom Generator from any One-way Function
- Lower Bounds in a Parallel Model without Bit Operations
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- A Uniform Circuit Lower Bound for the Permanent
- Quantum Computability
- The Parallel Evaluation of General Arithmetic Expressions
- The effect of random restrictions on formula size
- Shrinkage of de Morgan formulae under restriction
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Communication Complexity
- The Golden Ticket
- Survey propagation: An algorithm for satisfiability
- On the Computational Complexity of Algorithms
- Paths, Trees, and Flowers
- Deciding Positivity of Littlewood--Richardson Coefficients
- A machine program for theorem-proving
- On the restricted ordinal theorem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
