Questions tagged [np]

NP stands for Nondeterministic Polynomial time.

Filter by
Sorted by
Tagged with
17
votes
2answers
685 views

Hardness of parameterized CLIQUE?

Let $0\le p\le 1$ and consider the decision problem CLIQUE$_p$ Input: integer $s$, graph $G$ with $t$ vertices and $\lceil p\binom{t}{2} \rceil$ edges Question: does $G$ contain a clique on at ...
-2
votes
2answers
706 views

At last P != NP or not [duplicate]

Possible Duplicate: Is the recent proof that P != NP correct? some weeks ago I heard a news that some one proof that P != NP (link1 - link2) andsome days later I heard that he was wrong (I can't ...
14
votes
3answers
1k views

Is there a complexity theory analogue of Rice's theorem in computability theory?

Rice's theorem states that every nontrivial property of the set recognized by some Turing machine is undecidable. I am looking for complexity-theoretic Rice-type theorem that tells us which ...
3
votes
1answer
205 views

Sparsity of Horn satisfiability?

Is the set of satisfiable Horn formulas sparse? A sparse language contains a polynomially bounded number of srings at every length.
26
votes
3answers
980 views

Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?

Are there any natural problems in $NP \cap coNP$ that are not (known to be/thought to be) in $UP \cap coUP$? Obviously the big one everyone knows about in $NP \cap coNP$ is the decision version of ...
11
votes
3answers
591 views

Two Variants of NP

Here are two variations on the definition of NP. They (almost certainly) define distinct complexity classes, but my question is: are there natural examples of problems that fit into these classes? (...
18
votes
1answer
635 views

Best known joint containments for/by NP and Parity-P?

Parity-P is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero ...

1 2
3