Questions tagged [np]

Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.

44 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
235 views

Are there consequences for P ≠ NP that are unintuitive?

It's often regarded that the most intuitive answer to the question of $P$ vs $NP$ is that $P ≠ NP$. This is often illustrated with some consequences that would follow if $P = NP$ were true. Things ...
4
votes
0answers
77 views

Matrix covering by squares

I wonder about the following decision problem : Instance: We consider a $n\times p$ matrix $M$ of zeros and ones, and two integers $N$ and $k$. Question: is it possible to cover all the ones of the ...
4
votes
0answers
95 views

Maximum coloring of a graph with paths through uncolored vertices

Last night, I had a dream involving an intelligent spider which was only able to communicate by crawling around on a grid of words/phrases, like this one: When I woke up, I wondered why some of the ...
4
votes
0answers
1k views

$NP = PSPACE$ and what that would mean about $PH$

So, a paper showed up on arXiv: https://arxiv.org/abs/1609.09562 The above states in the abstract that it contains a proof that $NP = PSPACE$ Since $NP \subseteq PH \subseteq PSPACE$, that would ...
4
votes
0answers
211 views

If BQP is contained in any level of the Polynomial Hierarchy, does it then follow that $NP \subseteq BQP$ implies $PH \subseteq BQP$?

I think this is implied in this paper by Aaronson (http://www.scottaaronson.com/papers/bqpph.pdf) but I am not sure. Begin with $NP \subseteq BQP$ (*) $\Sigma_{2}^{P} = NP^{NP} \subseteq BQP^{BQP} = ...
3
votes
0answers
23 views

$NP$, $P^{TFNP}$ and $P^{UP}$

Is it possible $NP\subseteq P^{TFNP}$ holds or $NP\subseteq P^{UP}$ holds without the polynomial hierarchy collapsing? Is there problems in one of each of the classes from $NP$, $P^{UP}$ and $...
3
votes
0answers
31 views

Reachability games with banned vertex repetition

I have bumped into this problem while working on something model checking related and can't seem to find materials or efficient solutions for it. I couldn't even find a name for it. We have a ...
3
votes
0answers
48 views

Karp hardness of a module in a graph

DEFINITION: A set of vertices $A\subseteq V$ in a graph $G(V,E)$ is called a module if it satisfies the following property: For every $v\in V\setminus A$, either $A\subseteq N(v)$ or $A\cap N(v)=\...
3
votes
0answers
145 views

Complete problems in NP∩coNP

I often read in Complexity literature that NP∩coNP is unlikely to have any complete problems. Is that unlikelihood "proved" ? By proved, I mean that there would be a theorem that would relate the ...
2
votes
0answers
37 views

NP-completeness of Induced disjoint paths between a set of sources and a set of sinks

In a given undirected graph $G(V,E)$, a set of $k$ paths is said to be induced if: They are vertex-disjoint. Each one is itself an induced path. No edge connects two vertices of two different paths. ...
2
votes
0answers
27 views

Reducible from vertex cover for only some inputs

Suppose I have an NP problem, $\text{PROBLEM}(n)$, such that for certain values of $n$ I can get a reduction from vertex cover with $n$ vertices, and for others such a reduction is not possible (if $\...
2
votes
0answers
27 views

Karp hardness of two vertex sets in a digraph

Given a digraph $G(V,A)$ and a number $k$, we want to find two vertex subsets $S,T\subseteq V$ such that: $|S|+|T|=k$ For every $v\notin S\cup T$, $v$ has no arcs coming to $S$, and no arcs coming ...
2
votes
0answers
33 views

A particular type of SOS hardness proof

Is there an example of a sum of squares (SOS) hardness proof where the constraint is something non-trivial (like with some polynomial constraint) rather than just imposing the the typical $x_i^2 =1$ ...
2
votes
0answers
107 views

Karp reduction between FACTORING and a variant of it

Consider the following variant of the FACTORING problem (given N,M decide whether N has a prime factor less than M): MULTIPLE-FACTORING: Given three integers $1 \leq K \leq M \leq N$ decide if there ...
1
vote
1answer
18 views

Prove a TM problem is NP-complete

Question: Show that $T_{NP}$ is NP-complete, where $$T_{NP} = \{m\#w\#^c\mid M_m\text{ is an NTM};M_m(w)\text{ has an accepting computation of $\leq$ c steps}\}$$ This question looks weird to me ...
1
vote
1answer
23 views

Is there any importance in problems whose witness for membership in a set, cannot be bounded by a polynomial?

The class NP can be defined as a polynomially bounded relation $R$. Where $x \in R$ if there exists some $y$ that has length bounded by $p(|x|)$, where $p$ is some polynomial. Why do we not study the ...
1
vote
0answers
48 views

How to reduce independent set to longest path

A friend and I have tried for several hours to try and find a reduction from independent set to longest path, but the results have not been fruitful. We have tried many methods of graphing and ...
1
vote
0answers
34 views

Testing if a 4-regular graph can be decomposed into two edge-disjoint Hamiltonian cycles

Given a 4-regular graph, is it NP-complete to test whether it can be decomposed into two edge-disjoint Hamiltonian cycles?
1
vote
1answer
86 views

Non-constructive $NP$-completeness proof

Is there any known $NP$-complete problem which hardness proof is non-constructive. A constructive $NP$-completeness proof is a proof that $L_1\leq_p L_2$ by a reduction $r$ and from the argument ...
1
vote
0answers
44 views

Karp hardness of a simply equidistant vertex set

Following the success of the previous question: Karp hardness of an equidistant vertex set I continue to propse yet another computational problem. This time, we modify the notion of an equidistant ...
1
vote
0answers
56 views

Decision problems with verifiable proofs but not in polynomial time

NP is a class of decision problems for which one can present a "certificate" that can be verified in polynomial time. Are there any decision problems that have such "certificates" that can be ...
1
vote
0answers
40 views

A question about SOS duality

Let us start with the optimization question, \begin{eqnarray*} min \{ c \vert c - f \in SOS_d \} \end{eqnarray*} for some function $f : \{0,1\}^n \rightarrow \mathbb{R}$ and $SOS_d $ being the cone ...
1
vote
0answers
85 views

Complexity lower bounds via Cook reductions

Karp reduction (polynomial-time many one) is used in complexity theory to define NP-completeness. However, Cook reductions (polynomial-time Turing) is more powerful and intuitive from information ...
0
votes
0answers
21 views

Problem in NP: $EQ1 = \{(p_1,…,p_n): \exists x_1,…,x_m\in Z \ p_1(x_1,…,x_m)=…=p_n(x_1,…,x_m)=0. \}$

I have to following problem to show is in NP class. $EQ1 = \{(p_1,...,p_n): \exists x_1,...,x_m\in Z \ p_1(x_1,...,x_m)=...=p_n(x_1,...,x_m)=0. \}$ Here $p_1,...,p_n$ are polynomials in m ...
0
votes
0answers
61 views

If any problem in NP is not in P then NP C ∩ P = ∅

If any problem in NP is not in P then NPC ∩ P = ∅ The proof is: We have $X ∈ NP$ and $X \not\in P$. Assume $Y ∈ NP C ∩ P$. As $X ≤_P Y$ we have $X ∈ P$, which is a contradiction. I have not clear ...
0
votes
0answers
45 views

Which is the most similar NP classic problem, if any exists, to this one?

Consider a given set $W = \{w_1, w_2,...,w_N\}$ of weights, such that $\sum_{i=1}^N w_i = 0$. Consider the given set of mutually different elements $A=\{a_1,a_2,...,a_M\}$ with $M\leq N$. Consider the ...
0
votes
0answers
22 views

NP problem solving

Prove that every NP problem is solvable in $O(2^{n^{k}})$ where $k$ is constant. My approach was that, let's look at the 3-SAT problem. We can solve it by bruteforce in $O(2^n)$, where $n$ is ...
0
votes
0answers
45 views

Intersection of decision problems?

Say we have two problems $\Pi_1\in NP$ and $\Pi_2\in coNP$. Where does $\Pi_1\cap\Pi_2$ live?
0
votes
0answers
58 views

Finding reduction to prove that a language is NP-complete

I need to prove that the following problem is NP-complete: We have $n$ diplomats from $n$ countries and we need to seat them around a round table. We also get a list of diplomats who don't get along ...
0
votes
0answers
63 views

Karp Reduction L1 ≤p L2

Given: $L_1 = \{0^k1^k|k \in \mathbb{N}\}$ $L_2= \{1\}$ $L_1 \leq_p L_2$ There must be a function $$f:Σ^* \rightarrow Σ^*$$ such that $$w \in L_1 \iff f(w) ∈ L_2$$ Let's say a word in $L_1$ is ...
0
votes
0answers
69 views

Circuit-sat reduction to 3-SAT

I'm trying to reduce this example from Circuit-sat to 3-Sat, but I got stuck. Can some one give a brief explanation step by step? Tree: schema My attempt:
0
votes
0answers
379 views

How to use SAT reductions to prove set-splitting problem is NP-Complete?

I am having a difficulty proving that the set splitting problem is NP-complete using SAT. Suppose S = {1,2,3,4} and C is a collection of subsets of S, say C1 = {1,2}, C2 = {3,4}, C3 = {1,3,4}. Each ...
0
votes
0answers
60 views

Proving P and NP on problems formulated as languages

To prove that a certain problem is in P we have to give an algorithm that decides or solves it in polynomial time. To prove that a problem is in NP an algorithm must exist so that it can check whether ...
0
votes
0answers
149 views

Prove that Vertex Cover belongs to NP

How to prove that the problem VERTEX-COVER belongs to $NP$? The problem VC is defined as follow: INSTANCE: Graph $G = (V,E)$ and an integer $k$ PREDICATE: Is there a subset $V_1 \in V $ s.t $\...
0
votes
0answers
150 views

Proving SAT is in L

How to prove that SAT is in L if and only if NP=L? I know that reducing SAT in cook-levin theorem is computable in deterministic linear space . How to do it in log space? Any reference will also help.
0
votes
0answers
958 views

NP Completeness: definition of search problem: Existence and Infinite Search space

For NP completeness proofs/reductions, I need to establish that the problem is a "search problem"... However, the definitions seem to be somewhat vague. If the definition of the search problem is: ...
0
votes
0answers
317 views

Need help reducing 1-in-3-SAT to show a problem is NP-complete

This is the original problem: And this is 1-in-3-SAT: I am using the 1-in-3-SAT problem (Pc) to reduce from, in order to prove that the original problem (P) is ...
0
votes
0answers
232 views

prove that the satisfiability problem with each clause containing at most 3 literals, denoted by ≤3SAT, is NP-complete

I've tried to prove it for several days but I can't make sure if it is equivalent to max-3-SAT problem? This problem seems similar to the proof of SAT ∝ 3-SAT except the case where there are more than ...
0
votes
0answers
273 views

Why do we need cook reductions?

I have a question about cook reductions and karp reductions. Which is the stronger form? As a cook reduction reduces a search problem to a decision problem which can then be reduced using karp ...
0
votes
0answers
112 views

If NP is easy on average then does it mean P=NP?

If $NP=RP$ then $NP$ is easy on average. Then from point $1$ in abstract in http://lance.fortnow.com/papers/files/derand.pdf which says $NP$ is easy on average implies $P=BPP$ do we have $NP=RP\...
0
votes
0answers
124 views

How not to prove that P ≠ NP implies NP ≠ PSPACE

Let's define the two variants of the Travelling salesman problem: $TSP_{opt}$ : Give me the shortest tour $TSP_{dec}$ : Is there a tour of $l$ or shorter (Yes/No) Now assume $P \neq NP$: Since $...
0
votes
0answers
59 views

How to solve a problem that is even hard to approximate?

I have a problem that is NP-hard and even NP-hard to approximate within a factor $n^{1-\varepsilon}$ $\forall \varepsilon > 0$. I'm looking now just for approaches that can help me to design a "...
-1
votes
1answer
42 views

3-Coloring Graph problem

Can we prove that the 3 coloring graph problem (where no two adjacent nodes have same color) is NP instead of NP-complete? $$\mathrm{3COLOR} = \{\langle G \rangle \mid G \text{ is colorable with 3 ...
-1
votes
1answer
75 views

Showing that given a graph $G$, does it exists a clique in $G$ of length $\ge k$" for a given $k\in\mathbb{N}$ is NP-complete

Let be the following problem : "Given a graph $G$, does it exists a clique in $G$ of length $\ge k$" for a given $k\in\mathbb{N}$. Show that it is NP-Complete I know how to show that a set of ...