Questions tagged [np]

NP stands for Nondeterministic Polynomial time.

Filter by
Sorted by
Tagged with
35
votes
1answer
1k views

NP-Completeness of the decision problem for the generalized 15-puzzle

I am interested in the natural generalization of the famous 15-puzzle, where you have to slide blocks until you have sorted all given numbers (usally there is a gap of 1 block). Now the ...
29
votes
3answers
2k views

A decision problem which is not known to be in PH but will be in P if P=NP

Edit: As Ravi Boppana correctly pointed out in his answer and Scott Aaronson also added another example in his answer, the answer to this question turned out to be “yes” in a way which I had not ...
29
votes
2answers
2k views

NP-intermediate problems with efficient quantum solutions

Peter Shor showed that two of the most important NP-intermediate problems, factoring and the discrete log problem, are in BQP. In contrast, the best known quantum algorithm for SAT (Grover's search) ...
28
votes
7answers
2k views

Nontrivial membership in NP

Is there an example of a language which is in $NP$, but where we cannot prove this fact directly by showing that there exists a polynomial witness for membership in this language? Instead, the fact ...
28
votes
3answers
1k 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 ...
28
votes
6answers
1k views

Natural NP-complete problems with "large" witnesses

The question on cstheory "What is NP restricted to linear size witnesses?" asks about the class NP restricted to linear size $O(n)$ witnesses, but Are there natural NP-complete problems in which (...
27
votes
2answers
1k views

Reasons to believe $P \ne NP \cap coNP$ (or not)

It seems that many people believe that $P \ne NP \cap coNP$, in part because they believe that factoring is not polytime solvable. (Shiva Kintali has listed a few other candidate problems here). On ...
26
votes
4answers
2k views

Best known deterministic time complexity lower bound for a natural problem in NP

This answer to Major unsolved problems in theoretical computer science? question states that it is open if a particular problem in NP requires $\Omega(n^2)$ time. Looking at the comments under answer ...
25
votes
2answers
1k views

Is there an NP-complete language that contains precisely half of the n-bit instances?

Is there a (preferably natural) NP-complete language $L\subseteq \{0,1\}^*$, such that for every $n\geq 1$ $$|L\cap \{0,1\}^n|=2^{n-1}$$ holds? In other words, $L$ contains precisely half of all $n$-...
25
votes
1answer
706 views

What is $\mathsf{NP}$ restricted to linear size witnesses?

This is related to the question Is the Witness Size of Membership for Every NP Language Already Known? Some natural $\mathsf{NP}$(-complete) problems have linear length witnesses: a satisfying ...
23
votes
3answers
1k views

How much would a SAT oracle help speeding up polynomial time algorithms?

Access to a $SAT$ oracle would provide a major, super-polynomial speed-up for everything in ${\bf NP}-{\bf P}$ (assuming the set is not empty). It is less clear, however, how much would $\bf P$ ...
22
votes
3answers
6k views

Implications of proving NP=RP on complexity theory

Edit: As indicated below by Mahdi Cheraghchi and in the comments, the paper has been withdrawn. Thanks for the multiple excellent answers on the implications of this claim. I, and hopefully others, ...
20
votes
1answer
673 views

Problems in NP but not in Average-P/poly

The Karp–Lipton Theoem states that if $\mathsf{NP} \subset \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma^P_2}$. Therefore, assuming separations between $\mathsf{\Sigma^P_2}$ and $\...
19
votes
2answers
1k views

Are there known NP-complete problems, neither NP-hard in the strong sense nor having pseudopolynomial algorithm?

In their paper (p. 503) Garey and Johnson remark: ... there could exist an NP-complete problem which is neither NP-complete in the strong sense nor solvable by a pseudo-polynomial time algorithm ......
19
votes
2answers
2k views

Is there a non-deterministic linear time algorithm for CNF-SAT?

The decision problem CNF-SAT can be described as follows: Input: A boolean formula $\phi$ in conjunctive normal form. Question: Does there exist a variable assignment that satisfies $\phi$? I'm ...
18
votes
1answer
2k views

Algorithm whose running time depends on P vs. NP

Is there a known, explicit example of an algorithm with the property such that if $P\neq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?
18
votes
1answer
725 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 ...
17
votes
2answers
693 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 ...
17
votes
1answer
763 views

Complexity of a switch network problem

A switch network (the name is invented) is made with three types of nodes: one Start node one End node one or more Switch nodes The switch node has 3 exits: Left, Up, Right; has two states L and R ...
16
votes
1answer
566 views

Integer linear programming in logarithmic number of variables

I read that integer linear programming is solvable in polynominal time if the number $n$ of variables is fixed, i.e. $n \in O(1)$. If the number of variables grows logarithmically, i.e. $n \in O(\...
15
votes
2answers
445 views

(How) Could we discover/analyze NP problems in the absence of the Turing model of computation?

From a purely abstract math/computational reasoning point of view, (how) could one even discover or reason about problems like 3-SAT, Subset Sum, Traveling Salesman etc.,? Would we be even able to ...
15
votes
1answer
892 views

$NP$-complete problem with quasi-polynomial bound on the number of solutions

FewP is the class of $NP$-problems with polynomial bound on the number of solutions (in the input size). There is no known $NP$-complete problem in $fewP$. I am interested in how far we can stretch ...
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 ...
14
votes
1answer
1k views

Are there "NP-Intermediate-Complete" problems?

Assume P $\ne$ NP. Ladner's Theorem says that there are NP Intermediate problems (problems in NP that are neither in P nor NP-Complete). I have found some veiled references online that suggest (I ...
14
votes
4answers
947 views

Are there any known NP problems which are conjectured to be exponentially hard on average?

ETH states that SAT cannot be solved in the worst case in subexponential time. What about average case? Are there natural problems in NP that are conjectured to be exponentially hard in the average ...
14
votes
2answers
727 views

Are There Highly Symmetric NP- or P-complete Languages?

Does there exist $L$, an NP- or P-complete language which has some family of symmetry groups $G_n$ (or groupoid, but then the algorithmic questions become more open) acting (in polynomial time) on ...
14
votes
1answer
540 views

Does PSPACE-completeness imply approximation hardness?

It is mentioned in a comment in another cstheorySE post that PSPACE-completeness imply APX-hardness. Can anyone please explain/share a reference for it? Is this "tight"? (i.e., are there PSPACE-...
13
votes
2answers
2k views

Is the half-filled magic square problem NP-complete?

Here is the problem: We have a square with some numbers from 1..N in some cells. It's needed to determine if it can be completed to a magic square. Examples: ...
13
votes
1answer
551 views

Is the Witness Size of Membership for Every NP Language Already Known?

The question occurred to me when I get Dana Moshkovitz answer to another topic. Let $L$ be an NP Language, and let $R_L$ be the respective NP relation. We know that there exists some polynomial $p$ ...
12
votes
2answers
675 views

Euclidean TSP in NP and square root complexity

In this lecture notes by Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf, it is said that we don't know if Euclidean TSP is in NP: The reason being that we do not ...
12
votes
2answers
499 views

Are there knot theoretic formulations of NP complete problems?

Are there NP complete(or even NP-hard, or NP) problems that have good topological properties to study. Do NP problems have knot theoretic formulations? We know about #$P$ results about the Jones ...
12
votes
1answer
681 views

Conditions for tractability of 3SAT-Satisfiability

What I'm wondering specifically is if there is an interesting condition on the percentage of assignments that satisfy a 3SAT formula to guarantee that such problems are tractable. Suppose for example ...
12
votes
3answers
410 views

NP-complete graph property that is hereditary, but not additive?

A graph property is called hereditary if it closed with respect to deleting vertices (i.e., all induced subgraphs inherit the property). A graph property is called additive if it is closed with ...
12
votes
0answers
475 views

Is satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ NP Complete?

Question I would like to show that satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ is NP-Complete. Consider $L= \{(\bar{y},r):\exists \bar{x} \text{ such that } \sum_{i=1}^{n}{x_i^{y_i}}=r\}$. Where $\...
11
votes
1answer
1k views

Non-Uniform vs. Uniform Adversaries

This question arose in the context of cryptography, but below I will present it in terms of complexity theory, since people here are more acquainted with the latter. This question is related to ...
11
votes
1answer
286 views

When was co-NP introduced for the first time?

My best finding is Pratt's 1975 article. Is there any earlier mention of co-NP?
11
votes
3answers
337 views

Is there a simple game with asymmetric complexity?

Consider full information two-player combinatorial games that end after a polynomial number of moves, and in an alternating way, the players picks from a finite number of allowed moves. The usual ...
11
votes
3answers
606 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? (...
11
votes
1answer
710 views

NP vs co-NP and second-order logic

Assume that NP=co-NP and polynomial $p(x)$ bounds the length of the proof of unsatisfiability for a 3-CNF instance $x$. Then are there any results on what form any proof of unsatisfiability for $x$ of ...
11
votes
1answer
238 views

What do dichotomy theorems feed on?

It is well known that certain classes of NP-problems have dichotomy theorems, which guarantee that every task in the class is either NP-complete or is in P. The best known such result is Schaefer's ...
10
votes
3answers
386 views

Graph theoretic restriction to Proofs in Proof Complexity Theory

Proof complexity is a most basic area of computational complexity theory. An ultimate purpose of this area is to prove $NP\neq coNP$, that is, any prover cannot give a proof of unsatisfiability of ...
10
votes
0answers
253 views

Have people looked for parameterized algorithms for problems that are not in NP?

Are there problems that are not in NP (e.g., NEXP-complete problems) but admit FPT algorithms for a reasonable parameterization (and specifically, the standard parameterization of a problem -- the ...
9
votes
1answer
1k views

Does every Turing-recognizable undecidable language have a NP-complete subset?

Does every Turing-recognizable undecidable language have a NP-complete subset? The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an ...
9
votes
0answers
241 views

Complexity of a problem over acyclic context-free grammars

Let $G$ be an acyclic, context-free grammar over a fixed alphabet $\Sigma=\{a_1,\dots,a_k\}$ with the restriction (without loss of generality) that $|w|=2$ for each rule $A\to w$ in the grammar. ...
8
votes
1answer
1k views

Intersection of languages in NP

Can intersection of two languages in NP which are not NP complete be NP complete? Can intersection of two languages in coNP which are not coNP complete be coNP complete? Can intersection of two ...
8
votes
1answer
719 views

Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?

If it is unknown, are there reasons to believe that they might not be equal?
8
votes
0answers
791 views

Is this minimization problem NP-Complete?

We are given an $n \times (n + k)$ matrix $A$, with entries in GF(2), of the form $A =[I_n\ B]$, where $I_n$ is the $n \times n$ identity matrix, and $B$ has no "zero" rows or columns. The problem is ...
7
votes
1answer
348 views

"Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org?

Do you believe this paper is worthy of arXiv.org? I have searched via Google, and to my knowledge, no one else has this result. I'm not asking you to fully scrutinize the paper, I'm just asking if you ...
7
votes
1answer
196 views

Can NP-hard statements be proved by PCPs that only involve reading 2 bits?

For non-negative integers q, let PCP(q) denote the set of promise problems that have polynomial-length probabalistically checkable proofs over the binary alphabet in which the verifier only reads q ...
7
votes
1answer
125 views

Literature for restrictions that make NPC-Problems to P

The boolean satisfiability problem is in $\mathcal{NPC}$. But if you only get Horn clauses, it is in $\mathcal{P}$. I've already heard similar statements. Do you know a more general statement when ...