NP stands for Nondeterministic Polynomial time.

learn more… | top users | synonyms

1
vote
0answers
72 views

About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube

Naively, in my very limited awareness, it feels that the Max-CUT is a very "special" NP-Hard problem because for a graph with edge-set $E$, it can be written as the question of trying to maximize a $n$...
5
votes
1answer
113 views

Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis

The Berman Hartmanis conjecture which formally states that there is an isomorphism for two $NP$ complete languages $L_{1}$, and $L_{2}$, the isomorphism is a bijective function $f()$ such that $f()$ ...
6
votes
1answer
127 views

Does p-isomorphism preserve phase transition?

Consider two NP-complete languages that are polynomial-time isomorphic. If we know that one of them exhibits phase transition (with respect to some order parameter), does this imply that the other ...
2
votes
0answers
70 views

An NP-complete variant of factoring and relation to factoring [closed]

After reading this post An NP-complete variant of factoring. I come up with a question. To summerize the post, we have the factoring problem (F) which ask for a number $p$ that is prime and divides ...
-5
votes
1answer
53 views

non deterministic algorithm always find the right solution? [closed]

i'm confused since i see some books mention the NP time algorithms as "very lucky" that means it always finds the right path? also can someone explain the coming points to me please... A ...
7
votes
1answer
303 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 ...
2
votes
0answers
101 views

Are ill-posed inverse problems in NP?

I'm a physicist who works on inverse problems; I'll explain what these are by means of an example. Consider an object whose refractive index is known; then, the problem of computing scattered ...
6
votes
3answers
353 views

Natural NP-complete problems with high density?

(This question is related to a previous one, see the discussion in "Almost easy" NP-complete problems, but it may also be of independent interest, so I post it as a separate question.) Let ...
7
votes
0answers
176 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. ...
15
votes
2answers
347 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 ...
10
votes
1answer
168 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 ...
3
votes
0answers
70 views

Functional oracles

In the traditional oracle Turing machine, the oracle is specified as a decision problem. Roughly speaking, one puts a string in the oracle tape, and asks whether it is true or false. I am wondering ...
21
votes
3answers
486 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$ ...
5
votes
0answers
79 views

Question about a unary language construction

For any language $L$, let us define another language $Tally(L)$, as follows: $$Tally(L)=\{1^n\;|\;\exists x \;\mbox{with}\; x\in L \;\mbox{and}\; |x|=n\}$$ That is, $Tally(L)$ encodes whether there is ...
3
votes
1answer
404 views

If BQP contains NP, does this mean that P=NP?

There is a question raised by Scott Aaronson in one of his papers [1]: "Could we show that if NP ⊆ BQP, then the polynomial hierarchy collapses?". Assuming the answer is yes, and it is also know that ...
1
vote
1answer
174 views

Is finding whether k different perfect matchings exist in a bipartite graph co-NP?

Few definitions first. The co-NP problem is a decision problem where the answer "NO" can be verified in polynomial time. The perfect matching in a bipartite graph is a set of pairs of nodes (a pair is ...
1
vote
0answers
170 views

Finding an equivalent NP-complete instance for this game-theory problem

I apologize if this question is not a good fit for CSTheory. I'm a PhD student who has just started out and I'm working on a game-theory problem in one of my classes. Although my professor hasn't ...
1
vote
0answers
162 views

Is there a reduction from a 0-1 knapsack problem to the unbounded problem?

As we know, an unbounded knapsack problem could be described as: $\max \sum_{i=1}^nc_1x_i$ s.t. $\sum_{i=1}^na_ix_i\le b$ $x_i\ge0,x_i\in\mathbb Z,i=1,\cdots,n$ And for an 0-1 knapsack problem, we ...
14
votes
1answer
393 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(\...
10
votes
3answers
296 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 ...
6
votes
1answer
126 views

Bounds on the size of the solution of a quadratic program

I am interested in a quadratic program of the form $$ \min x^T Q x $$ $$s.t.$$ $$ Ax \leq b $$ where $x$ is a vector with $n$ entries, the size of the maximal entry in $Q, A$, and $b$ is $\varphi$, $...
11
votes
3answers
279 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 ...
2
votes
2answers
204 views

Balls & Bins: A punishment and reward game

Consider a game where one has a set of bins $(b_1, b_2, ...)$, and each bin has an associated initial count of balls $(c_1, c_2, ...)$. The rules of the game are as follows: (1) Once a bin has a ...
1
vote
0answers
91 views

Properties of “second-order” NP (complete) languages

Reading the question Natural NP-Complete Problems with Large Witnesses, I was interested in this language: $L = \{ \varphi ~~:~~ \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ ...
7
votes
1answer
170 views

Minimal polynomial reduction of dominating set to max clique

Let $G$ be a simple undirected graph. Recall that $S \subseteq V(G)$ is a dominating set of $G$ if every vertex of $v \in V(G) \setminus S$ has a neighbour in $S.$ It is well known that it is NP ...
11
votes
2answers
252 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 ...
15
votes
1answer
724 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 ...
26
votes
6answers
802 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 (...
14
votes
1answer
392 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-...
3
votes
0answers
218 views

Does $P\neq NP$ imply any larger separation?

I've asked a similar question in cs.se, but didn't get a satisfying answer. Assuming $P\neq NP$, what can we say about the runtime of any algorithm for an $NP$-complete problem? Obviously, it means $...
11
votes
3answers
351 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 ...
27
votes
7answers
1k 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 ...
11
votes
1answer
635 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 ...
6
votes
1answer
142 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 ...
1
vote
1answer
192 views

Complexity of an edit distance problem

Given an array $A[1...n]$ of non-negative integers, we want to transform $A$ into $A'$ such that $|A[I] - A[I + 1]| \leq 1$ in the minimum number of operations. One operation consist of picking ...
-1
votes
1answer
210 views

Deciding whether a turning machine guaranteed to halt solves sat [closed]

Suppose I give as input a Turing machine M guaranteed to halt in time n^c on inputs of length n for a universal constant c. Is there a Turing machine that given any such M can decide whether M solves ...
7
votes
1answer
446 views

Public-key encryption without the assumption that $P \neq NP$

I'm not talking about the RSA, El-gamal, nor any specific encryption scheme. Rather, my question, as related to this and this threads, is why the idea of Public-Key encryption scheme cannot be secure ...
2
votes
1answer
157 views

Dividing users with certain files into 2 equal groups

I am framing a particular combinatorial question using users and files for better understanding. Let there be a universe of files $F$ = $\{f_1, f_2,\ldots,f_n\}$ and $2k$ users $\{u_1, u_2,\ldots, u_{...
26
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 ...
7
votes
1answer
297 views

Consequences and state-of-the-art of NP ≠ ZPP?

Consider the complexity classes $\mathsf{NP}$ and $\mathsf{ZPP}$. Whether the two classes are equal is an open question, but as far as I know, $\mathsf{NP} = \mathsf{ZPP}$ is not known to imply $\...
-1
votes
2answers
386 views

Intersection between sets

Assume that we have $p$ sets, with given sizes: $m_1,m_2,...,m_p$. The (distinct) elements in each set are taken from $N$ elements (where $m_1,m_2,...,m_p \le N$). A combination is defined as an ...
24
votes
4answers
1k 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 ...
33
votes
1answer
782 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 ...
8
votes
1answer
513 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 ...
10
votes
4answers
751 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 ...
6
votes
1answer
2k views

Guidelines to reduce general TSP to Triangle TSP

I am looking for the method / correct way to approach to reduce the traveling salesman problem to an instance of traveling salesman problem which satisfies the triangle inequality, ie: $D(a, b) \leq ...
7
votes
1answer
123 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 ...
6
votes
0answers
128 views

The relation between NP and IP(2pfa)

As far as I know, it is not known whether $ \mathsf{NP} \subseteq \mathsf{IP(2pfa)} $, where $ \mathsf{IP(2pfa)} $ is the class of languages having interactive proof systems with some two-way ...
2
votes
1answer
549 views

Is “meeting/room planning” NP-complete?

Short summary: The problem is to assign people to meetings at different days while respecting the capacities and (inter-day) constraints of the meetings. Each person can only attend at most one ...