Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,818
questions
229
votes
11answers
119k views
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct?
Also on topic: where else (on the internet) is its correctness being discussed?
Note: the focus of this question text has ...
137
votes
29answers
22k views
Problems Between P and NPC
Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? ...
89
votes
14answers
19k views
What kind of mathematical background is needed for complexity theory?
I am currently an undergraduate student, bound to graduate this year. After graduation, I am considering to work towards a TCS master/PhD. I have begun wondering what fields of mathematics are ...
86
votes
2answers
31k views
What is the actual time complexity of Gaussian elimination?
In an answer to an earlier question, I mentioned the common but false belief that “Gaussian” elimination runs in $O(n^3)$ time. While it is obvious that the algorithm uses $O(n^3)$ arithmetic ...
71
votes
8answers
9k views
Are runtime bounds in P decidable? (answer: no)
The question asked is whether the following question is decidable:
Problem Given an integer $k$ and Turing machine $M$ promised to be in P, is the runtime of $M$ ${O}(n^k)$ with respect ...
69
votes
7answers
4k views
Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)
Mathematicians sometimes worry about the Axiom of Choice (AC) and Axiom of Determinancy (AD).
Axiom of Choice: Given any collection ${\cal C}$ of nonempty sets, there is a function $f$ that, given a ...
68
votes
7answers
4k views
Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?
Currently, solving either a $NP$-complete problem or a $PSPACE$-complete problem is infeasible in the general case for large inputs. However, both are solvable in exponential time and polynomial space....
68
votes
4answers
32k views
Why is 2SAT in P?
I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? ...
65
votes
11answers
5k views
What are good references to understanding the proof of the PCP theorem?
I'm familiar with a lot of results that use the PCP theorem (mainly in approximating algorithms), but I've never come across a clear explanation of the PCP theorem (ie, that $\mathsf{NP} = \mathsf{PCP}...
65
votes
5answers
2k views
Problems that can be used to show polynomial-time hardness results
When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find ...
64
votes
1answer
3k views
More on PH in PP?
A recent question by Huck Bennett asking whether the class PH was contained in the class PP, received somewhat contradictory answers (all true, it seems). On one hand, several oracle results were ...
62
votes
12answers
3k views
Parameterized complexity from P to NP-hard and back again
I'm looking for examples of problems parametrized by a number $k \in \mathbb{N}$, where the problem's hardness is non-monotonic in $k$. Most problems (in my experience) have a single phase transition, ...
62
votes
8answers
3k views
What is the complexity class most closely associated with what the human mind can accomplish quickly?
This question is something I've wondered about for a while.
When people describe the P vs. NP problem, they often compare the class NP to creativity. They note that composing a Mozart-quality ...
57
votes
9answers
24k views
Explain P = NP problem to 10 year old
It is my first question on this site. I am taking a master's course on theory of computation. How you would explain P = NP problem to a 10 year old child and why it has such a monetary reward on it?
...
57
votes
6answers
3k views
Theoretical explanations for practical success of SAT solvers?
What theoretical explanations are there for the practical success of SAT solvers, and can someone give a "wikipedia-style" overview and explanation tying them all together?
By analogy, the smoothed ...
56
votes
7answers
4k views
For which problems in P is it easier to verify the result than to find it?
For (search versions) of NP-complete problems, verifying a solution is clearly easier than finding it, since the verification can be done in polynomial time, while finding a witness takes (probably) ...
56
votes
3answers
2k views
Surprising algorithms for counting problems
There are some counting problems which involve counting exponentially many things (relative to the size of the input), and yet have surprising polynomial-time exact, deterministic algorithms. Examples ...
55
votes
2answers
4k views
Can one amplify P=NP beyond P=PH?
In Descriptive Complexity, Immerman has
Corollary 7.23. The following conditions are equivalent:
1. P = NP.
2. Over finite, ordered structures, FO(LFP) = SO.
This can be thought of as "...
53
votes
1answer
2k views
Is there a gap amplification type of result for the Graph Isomorphism Problem?
Suppose $G_1$ and $G_2$ are two undirected graphs on vertex set $\{1, \dotsc, n\}$. The graphs are isomorphic if and only if there is a permutation $\Pi$ such that $G_1 = \Pi(G_2)$, or more formally, ...
52
votes
4answers
4k views
Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?
This might be a subjective question rather than one with a concrete answer, but anyway.
In complexity theory we study the notion of efficient computations. There are classes like $\mathsf{P}$ stands ...
51
votes
4answers
5k views
What are the best current lower bounds on 3SAT?
What are the best current lower bounds for time and circuit depth for 3SAT?
50
votes
20answers
8k views
NP-hard problems on trees
Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include ...
49
votes
9answers
9k views
Best Upper Bounds on SAT
In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT."
I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time ...
48
votes
4answers
2k views
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
We know that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ and that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq $ $\mathsf{polyL}$, where $\mathsf{L}^2 = \mathsf{...
48
votes
3answers
4k views
An NP-complete variant of factoring.
Arora and Barak's book presents factoring as the following problem:
$\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$
They add, further ...
47
votes
5answers
7k views
Is the Chomsky-hierarchy outdated?
The Chomsky(–Schützenberger) hierarchy is used in textbooks of theoretical computer science, but it obviously only covers a very small fraction of formal languages (REG, CFL, CSL, RE) compared to the ...
47
votes
6answers
2k views
Ways for a mathematician to stay informed of current research in complexity theory
Complexity theory is a strong secondary interest of mine but it's not my primary research interest, so there is no hope for me to attend all the conferences, read all the blogs, and ensure that the "...
47
votes
0answers
2k views
Monotone complexity of s-t connectivity
In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide
whether there is a path between all $n^2$ pairs $...
46
votes
8answers
7k views
The importance of Integrality Gap
I always had trouble in understanding the importance of the Integrality Gap (IG) and bounds on it. IG is the ratio of (the quality of) an optimal integer answer to (the quality of) an optimal real ...
46
votes
4answers
13k views
Approximation algorithms for Metric TSP
It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time.
Is anything known about finding approximation solutions in ...
46
votes
4answers
4k views
Generalized Ladner's Theorem
Ladner's Theorem states that if P ≠ NP, then there is an infinite hierarchy of complexity classes strictly containing P and strictly contained in NP. The proof uses the completeness of SAT under many-...
46
votes
5answers
1k views
Are there Conservation Laws in Complexity Theory?
Let me start with some examples. Why is it so trivial to show CVP is in P but so hard to show LP is in P; while both are P-complete problems.
Or take primality. It is easier to show composites in NP ...
46
votes
0answers
1k views
Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?
If we assume the Exponential-Time Hypothesis, then there is no $2^{o(n)}$ algorithm for $n$-variable 3-SAT, and many other natural problems, such as 3-COLORING on graphs with $n$ vertices. Notice ...
45
votes
8answers
5k views
Obituaries of dead conjectures
I am looking for conjectures about algorithms and complexity that were viewed credible by many at some point in time, but later they were either disproved, or at least disbelieved, due to mounting ...
45
votes
3answers
5k views
Wikipedia-style explanation of Geometric Complexity Theory
Can someone provide a concise explanation of Mulmuley's GCT approach understandable by non-experts? An explanation that would be suitable for a Wikipedia page on the topic (which is stub at the moment)...
44
votes
10answers
4k views
Kolmogorov complexity applications in computational complexity
Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$)...
43
votes
3answers
3k views
What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?
Background
The computation over real numbers are more complicated than computation over natural numbers, since real numbers are infinite objects and there are uncountably many real numbers, therefore ...
43
votes
3answers
3k views
Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem
The Graph Isomorphism problem (GI) is arguably
the best known candidate for an NP-intermediate problem.
The best known algorithm is sub-exponential algorithm
with run-time $2^{O(\sqrt{n \log n})}$. ...
asked Nov 25 '13 at 12:00
Mohammad Al-Turkistany
20.5k4 gold badges57 silver badges144 bronze badges
42
votes
22answers
5k views
What hierarchies and/or hierarchy theorems do you know?
I am currently writing a survey on hierarchy theorems on TCS. Searching for related papers I noticed that hierarchy is a fundamendal concept not only in TCS and mathematics, but in numerous sciences, ...
42
votes
5answers
1k views
The cozy neighborhoods of "P" and of "NP-hard"
Let $X$ be an algorithmic task. (It can be a decision problem or an optimization problem or any other task.) Let us call $X$ "on the polynomial side" if assuming that $X$ is NP-hard is known to imply ...
41
votes
12answers
2k views
Gröbner bases in TCS?
Does anyone know of interesting applications of Gröbner bases to theoretical computer science?
Gröbner bases are used to solve multi-variate polynomial equations, an NP-hard problem in general. I was ...
41
votes
7answers
6k views
Many-one reductions vs. Turing reductions to define NPC
Why do most people prefer to use many-one reductions to define NP-completeness instead of, for instance, Turing reductions?
41
votes
2answers
2k views
Are the problems PRIMES, FACTORING known to be P-hard?
Let PRIMES (a.k.a. primality testing) be the problem:
Given a natural number $n$, is $n$ a prime number?
Let FACTORING be the problem:
Given natural numbers $n$, $m$ with $1 \leq m \leq n$, ...
41
votes
3answers
5k views
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here.
I have asked some people who are ...
41
votes
3answers
1k views
A fixed-depth characterization of $TC^0$? $NC^1$?
This is a question about circuit complexity. (Definitions are at the bottom.)
Yao and Beigel-Tarui showed that every $ACC^0$ circuit family of size $s$ has an equivalent circuit family of size $s^{...
40
votes
3answers
6k views
P and NP classes explanation through lambda-calculus
In the introduction and explanation P and NP complexity classes often given through Turing machine.
One of the model of computation is the lambda-calculus.
I understand, that all of models of ...
40
votes
2answers
3k views
Semantic vs. Syntactic Complexity Classes
In his "Computational Complexity" book, Papadimitriou writes:
RP is in some sense a new and unusual kind of complexity class. Not any polynomially bounded nondeterministic Turing machine can be the ...
39
votes
3answers
2k views
Why are mod_m gates interesting?
Ryan Williams just posted his lower bound on ACC, the class of problems that have constant depth circuits with unbounded fan-in and gates AND, OR, NOT and MOD_m for all possible m's.
What's so ...
39
votes
5answers
1k views
Is there a logic without induction that captures much of P?
The Immerman-Vardi theorem states that PTIME (or P) is precisely the class of languages that can be described by a sentence of First-Order Logic together with a fixed-point operator, over the class of ...
39
votes
8answers
2k views
Formal notion for energy complexity of computational problems
Computational complexity includes the study of time or space complexity of computational problems. From the the perspective of mobile computing, energy is very valuable computational resource. So, Is ...