28
votes
What is so fundamental about polynomial functions that they are used to demarcate the Hardness boundary in NP complexity classes?
I see two main reasons:
Pragmatic reasons: It is a reasonable dividing line for most problems that arise in practice. Most problems that people encounter in practice seem to have time complexity ...
D.W.♦
- 169k
14
votes
Accepted
Do any decision problems exist outside NP and NP-Hard?
If $P = NP$, then any non-trivial language is NP-hard, and any trivial language belongs to NP. Hence, we do not get anything which is neither NP or NP-hard in this case.
If, however, $P \neq NP$, ...
- 3,649
14
votes
Accepted
Can any problem in P be converted to any other problem in P in polynomial time?
If by convert you mean reduce (through a Karp-reduction), then it is possible to reduce any problem $A$ in $P$ to any non-trivial problem $B$ in $P$.
Here "non trivial" means that $B$ has at least ...
- 29.8k
9
votes
What is the definition of P, NP, NP-complete and NP-hard?
P, NP, NP-complete and NP-hard are complexity classes, classifying problems according to the algorithmic complexity for solving them. In short, they're based on three properties:
Solvable in ...
9
votes
Accepted
Is every PSPACE-complete problem complete with respect to logspace reductions?
If every PSPACE complete problem is also complete under logspace reduction, then $\mathsf{P\neq PSPACE}$.
To see why, suppose for the purpose of contradiction that the definition of completeness ...
- 13.6k
9
votes
Accepted
Are all problems in P reducible to each other and equally difficult?
Well, there's reduce, and there's reduce.
Long story short: yes.
Caveat: reductions don't work well when the language in question is either "all strings", or "nothing", ie when $L=\...
- 18k
9
votes
Accepted
Are there problems that are hard to solve and also hard to check?
Yes. Any problem that is complete for a complexity class that strictly contains $\mathsf{NP}$ is an example.
The smallest class that is known to be different of $\mathsf{NP}$ would be $\mathsf{NEXP}$. ...
- 18.5k
8
votes
Accepted
Oracle Turing Machine EXP^EXP
No, $\mathsf{EXP^{EXP}=2EXP}$, a set of languages decidable in $O\left(2^{2^{\mathrm{poly}(n)}}\right)$ time.
This is just because you can give exponentially long input to an oracle which can solve ...
- 2,131
8
votes
Accepted
Is DISCRETE LOG a NP hard problem?
No one knows, but:
It is suspected that neither factoring nor discrete logarithm are NP-complete, but we have no proof. (Evidence for the suspicion: they are in NP $\cap$ coNP. See, e.g., https://...
D.W.♦
- 169k
7
votes
Accepted
Is complexity class $\Sigma^1_1$ from polynomial hierarchy decidable?
The confusion lies in using the same notation for the polynomial hierarchy and the arithmetical hierarchy.
The similarities are obvious, both notations talk about formulas with increasing quantifier ...
- 13.6k
7
votes
Accepted
Is exponentiation in P?
Your problem is not in P, for two different reasons:
P is a class of decision problems, but your problem is a function problem. Instead of P, you should consider its functional equivalent FP.
The ...
- 281k
7
votes
How hard is random SAT?
Theoretically, we don't know how hard k-SAT is; P ?= NP remains an open question. Empirically, random $k$-SAT at the critical clause/variable ratio for each $k$ seems to require exponentially more ...
- 8,247
7
votes
Accepted
Are any "standard" complexity classes uncountably infinite?
Nonuniform complexity class P/poly is uncountable. We can just choose for each input length its own circuit, so for any subset $S \subset \mathbb{N}$ the language $L_S = \{w \colon |w| \in S \}$ is in ...
- 445
7
votes
Accepted
Prove that "max independent set is larger than max clique" is NP-Hard
To prove the NP-hardness of the problem B under the polynomial-time many-one reduction, we can reduce from the maximum independent set problem.
We are given a graph of size $n$ and an integer $k$, to ...
- 2,962
7
votes
Accepted
What role does the lower bound play in the statement of Savitch's Theorem?
The proof relies on the following property: the time-complexity of a decider machine is at most exponential in its space-complexity. The bound assumptions, namely $f(n)\geq \log n$, are sufficient ...
- 5,514
6
votes
What does the complexity class $\mathsf{XP}$ stand for?
There is a slightly different description for XP which I personally find less misleading: "Polynomial time for each parameter". I believe the zoo page uses FPT instead of P for some formal reasons (...
- 2,368
6
votes
PSpace-completeness under PSpace reductions
Every language $X$ in PSPACE would be complete under your proposed definition, except for $\emptyset$ and $\Sigma^*$. You could reduce any PSPACE language $Y$ to $X$ by a reduction that ...
- 82.6k
6
votes
Accepted
Looking for a problem provably not in P
The time hierarchy theorem already does the diagonalization for you.
Let $X$ be any $\mathbf{EXP}$-complete problem. If $X\in\mathbf{P}$, then $\mathbf{EXP}=\mathbf{P}$, since we can solve any ...
- 82.6k
6
votes
If a language is contained in other langauge, is it of the same complexity?
No. $\Sigma^*\in\mathbf{P}$ and every langauge is a subset of that – even undecidable ones.
- 82.6k
6
votes
Accepted
Is there a complexity class QPP?
Yamakami showed in their paper Analysis of Quantum Functions that the quantum analog of PP is the same as classical PP. This is mentioned in the Wikipedia article on PP.
- 281k
6
votes
Is P/poly known to be in RE?
$P/poly$ is NOT a subset of $RE$. Specifically, the unary non-halting problem (i.e. given a Turing Machine encoded in unary, does it run forever?) is in $P/poly$ but not $RE$. In fact, every ...
- 30.4k
6
votes
Accepted
Are there any known W[3] or W[3]-hard problems?
There are a few examples in the answer to Natural complete problems in higher levels of the W-hierarchy. In particular, the W[3]-complete problem $p$-HYPERGRAPH-(NON)-DOMINATING-SET may be useful for ...
- 8,462
6
votes
Accepted
About a ℙ≠ℕℙ proof
What you showed is that no such program "Sat" can exist. Note that the complexity didn't matter here, since the argument still holds valid for any other complexity classes (a sign of this is ...
- 11.8k
6
votes
Is 2-coloring in NL or L?
The 2-coloring problem is $\mathsf{SL}$-complete. That means that there is a logspace reduction from 2-coloring to undirected accessibility (and conversely). See this paper for some references.
It was ...
- 18.5k
6
votes
Are all problems in P reducible to each other and equally difficult?
Any decidable problem can be reduced to any (non-trivial) decidable problem. Simply take a TM that would decide the source problem and replace its accept/reject halting states with a sequence that ...
- 1,804
5
votes
Accepted
Complexity Classes UP and US
Let me start with your third question. It seems that you don't quite understand the definitions of $\mathsf{UP}$ and $\mathsf{US}$, so let me repeat them here.
Definition of $\mathsf{UP}$. Property U....
- 281k
5
votes
CIRCUITSAT ∈ DTIME(2^n/n^c) ⟹ NP ≠ EXP?
$\mathsf{CircuitSat\in DTIME(2^n)}$ does not imply $\mathsf{NP\subseteq DTIME(2^n)}$ since the reduction might increase the input's size. Suppose for example that $L\in NP$ and the reduction from $L$ ...
- 13.6k
5
votes
Accepted
P=NP giving a deterministic algorithm for SAT
I like the way you think, but there's a gap in your attempt.
$\mathrm{P}$ and $\mathrm{NP}$ are classes of decision problems, i.e., computational tasks where the answer is either "yes" or "no". ...
- 82.6k
5
votes
Do relativized relations between complexity classes tell us anything about the nonrelativized relation?
I am by no means an expert, but 2 things come to mind:
Because if we know things like $A^L \neq B^L$, for some $L$, then a proof of $A = B$ need to be non-relativizing. This puts constrains on the ...
- 1,605
5
votes
Accepted
How to prove that existence of one-way functions implies P≠NP?
Suppose that P=NP, and that $f\colon \{0,1\}^* \to \{0,1\}^*$ is an arbitrary function computable in polynomial time. Suppose that $|x| = n$, and we are given $y = f(x)$. We will show how to find $z \...
- 281k
Only top scored, non community-wiki answers of a minimum length are eligible