# 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
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 ...
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 ...
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 ...
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 ...
211 views

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 ...
48 views

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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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:
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 ...
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 ...