Questions tagged [np]
Questions about decision problems that can be solved on nondeterministic Turing machines in time polynomial in the length of the input.
468
questions
1
vote
1answer
51 views
An NP-hard problem reduces to its complement?
I found this statement in a true/false test section:
Could someone explain in laymans why this is a true statement?
My understanding is that if $X$ is $\mathcal{NP}$-hard, then its complement must ...
0
votes
2answers
122 views
What is wrong with the following $P$ problem?
Our teacher gave us the following statement and we were wondering what is wrong with it.
Consider an array $A$ of $n$ distinct numbers. Since there are $n!$ permutations of $A$,
we cannot check ...
2
votes
1answer
55 views
Are problems in NP $\cap$ coNP less difficult than those in NP-complete?
I am taking a complexity class now, and I struggle to understand the concept of "hardness":
Assume that $L \in \textsf{NP } \cap \textsf{coNP}$. In means that under the assumption $\mathsf{NP} \neq \...
1
vote
1answer
2k views
A problem in NP but not NP-complete?
Graph isomorphisim is not proven to be NP-complete what would it imply if it were possible to prove that there are some problems which are in NP set of problems but not in NP-complete set.
0
votes
0answers
18 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 ...
2
votes
1answer
44 views
Assume that NP = DTIME(2^sqrt(n)), prove that DTIME(2^sqrt(n)) = DTIME(2^n)
I tried using the padding argument to prove such a thing (as it appeared in Arora's book), but I am not sure how this technique will help me here. I am trying to get to a contradiction to the Time ...
0
votes
0answers
31 views
How to know if a problem belongs to NP Class?
What I know (NOT strictly speaking): I know that there is an open question about the equality of P and NP Classes and as long as there is no known algorithm that solves NP problems in P time then we ...
3
votes
2answers
122 views
Union of a language in P and a language in NP\P
TRUE or FALSE Statement:
Assume that $P \neq NP$. Then, for all languages $L_1$ and $L_2$, if $L_1$ is in P and $L_2$ is in NP but not in P then $L_1 \cup L_2$ is in NP but not in P.
I have a ...
2
votes
1answer
271 views
O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force?
I came up with this O(V+E) algorithm for calculating the chromatic number X(g) of a graph g represented by an adjacency list:
Initialize an array of integers "colors" with V elements being 1
Using ...
3
votes
3answers
162 views
You prove that vertex cover reduces to some problem A, does that mean that A is NP-Complete?
My question is essentially the title. Let's say you have some random problem A. You prove that Vertex Cover (which is NP-Complete) reduces to A. You know nothing else about A besides that Vertex Cover ...
0
votes
0answers
18 views
Proving a problem is NP [duplicate]
I've seen in many textbooks if say we have a problem $Q$, we write a non-deterministic algorithm in polynomial time to solve problem $Q$, and then from that point it results that $Q\in NP$. Why is ...
1
vote
1answer
66 views
How to prove Shortest Common Superstring is NP-Hard
After some research and many youtube videos I have learnt that to prove a problem is NP-Hard; you would need to reduce that problem to known NP-Hard problems such as Subset Sum Problem, Halting ...
-1
votes
0answers
20 views
Prove that Hitting String is NP complete using 3 SAT
Given where x1,x2...xm are length-n strings over the alphabet {0,1,*} for some m,n> 1, check whether or not there exists a string y of length
n over the alphabet {0,1} such that y agrees with each xj ...
0
votes
1answer
73 views
P Vs NP can never be proven one way or the other!
Okay, so I was reading a bit about P vs NP problems. And I found out that proving P Vs NP is an NP problem.
And since if we prove that any problem in NP is a P that would mean that we have NP=P.
...
-1
votes
0answers
16 views
Translate arbitrary instance to 0/1 Knapsack [duplicate]
How can I translate (i.e. reduce) an arbitrary instance (S,t) of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of S are positive integers.
0
votes
0answers
58 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 ...
2
votes
1answer
20 views
Finding maximal cardinal independent set given oracle
The problem is given an oracle $O(G, k)$ that would say if graph G contains IS of size k devise an algorithm for finding independent set of max cardinality that makes poly number of calls to the ...
-1
votes
1answer
33 views
Another Subset sum problem
Verify that (S = {83, 88, 93, 67, 57, 89, 78, 51, 95, 98, 69, 49}, t = 492) is a positive instance of Susbset Sum.
1
vote
1answer
50 views
Subset sum to 0/1 knapsack
How can I translate (i.e. reduce) an arbitrary instance $(S, t)$ of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of $S$ are positive integers.
0
votes
1answer
34 views
Can someone pelase give a counter example of it? If a problem is in NP then there is no known polynomial time algorithm to solve it
Is there any known polynomial time algorithm to solve a problem which that problem is in NP. I was told is False but can't think of any counter example now.
5
votes
1answer
142 views
Using decision oracle to solve optimization problem of maximum polyomino tiling
So, this problem is a kind of variant of polyomino packing which has been discussed frequently elsewhere, but I haven't been able to find anything on my particular problem. Suppose we have a list of ...
2
votes
1answer
69 views
If A and B are NP-complete, then A ∪ B need not be NP-complete
I am studying the proof of this exercise (link)
There exist N P-complete languages A and B such that A ∪ B is not N P-complete. Example:
$A = \{1x : x ∈ SAT\} ∪ \{0x : x ∈ \{0, 1\}^∗\};$
$B =...
1
vote
1answer
535 views
How to prove graph isomorphism is NP?
I know that Graph Isomorphism should be able to be verified in polynomial time but I don't really know how to approach the problem. Any help would be appreciated.
0
votes
2answers
37 views
Decide whether an $n$-bit positive integer is composite
Question:
Given an $n$-bit positive integer. A decision problem is to decide whether it is composite. Is this problem in NP?
I know that for every composite number, a factor of the number is a ...
1
vote
1answer
14 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 ...
0
votes
0answers
44 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
21 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
42 views
Confusion about P versus NP [duplicate]
I'm sure that in my following question my reasoning is extremely simplistic and flawed, but I think if someone answered this it would help me understand what the P vs NP conundrum is. So here is my ...
-2
votes
2answers
81 views
Why haven't I solved the Travelling Salesman problem with the following argument using djikstras algorithm?
I claim to have solved the travelling salesman problem as follows.
(You will have to be familiar with djikstra's algorithm for this.)
1) I am about to start using djikstra's algorithm on any given ...
1
vote
2answers
144 views
P/NP - Polynomial Reduction vs Certificate
I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate.
How I understand polynomial reduction is that you can use it to ...
0
votes
2answers
50 views
An example of a computable problem that is not in P
I am trying to find a simple example of a problem that is computable but not in P, I know very well that it would be enough to get one in NEXTIME-complete however the problems that I find in this set ...
1
vote
1answer
85 views
if $L \in NP$ then its mapping reducible to HALT?
This is true because every language in $NP$ is decidable and therefore HALTS but how do I formally show this?
1
vote
1answer
61 views
How can i prove that MAX-CUT is in NP?
How can i show/explain/prove that Max-Cut is in NP?
"For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as ...
5
votes
2answers
2k views
is FIND WORDS in P?
FIND WORDS is the following decision problem:
Given a list of words L and a Matrix M, are all words in L also in M?
The words in M can be written up to down, down to up, left to right, right to left,...
2
votes
1answer
98 views
If X (an NP-hard problem) is polynomial-time many-one reducible to problem Y, then Y is NP-hard. Why is it the case?
According to this source,
If A is reduced to B and A ∈ class X, then B cannot be easier than X. This reduction is used to show if a problem belongs to NPH – just reduce some known NPH problem to ...
2
votes
1answer
101 views
Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G
In the textbook of CLRS, 'ch. 34.2 Polynomial-time verification' it says the following:
Suppose that a friend tells you that a given
graph G is hamiltonian, and then offers to prove it by giving ...
0
votes
0answers
43 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?
8
votes
3answers
479 views
Simple interepretation problem regarding Polynomial Hierarchy?
So $NP$ stands for problems where we have small verifiable witnesses for $YES$ instances and $coNP$ for small verifiable witnesses for $NO$ instances. How does this work for
$P^{NP}$
$NP^{NP}$
$coNP^...
1
vote
2answers
72 views
Is the certificate for primality testing polynomial in the length of the input?
If we were to assume that primality testing was in NP.
What would the certificate be, so that a polynomial time verifier can check the number X is indeed prime?
0
votes
1answer
58 views
Are there any “complete” languages in $coNP -NP$?
Suppose $coNP \neq NP$
language B would be called "complete" in $coNP-NP$ if:
$B\in coNP - NP$
$A\in coNP-NP \implies A\leq_pB$
Are there any "complete" languages in $coNP - NP$?
2
votes
1answer
45 views
D has polynomial verifyer, the certificate for any word $w \in D$ is at most O(|log w|) space. Prove $D \in P$
Given that a language D has a polynomial verifier,
and given that for every word $w \in D$, the length of the certificate $c$ is $O(\log|w|)$ space.
How can I prove that $D\in P$ ?
My idea was to ...
12
votes
2answers
3k views
Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)
I read about NPC and its relationship to PSPACE and I wish to know whether NPC problems can be deterministicly solved using an algorithm with worst case polynomial space requirement, but potentially ...
2
votes
2answers
121 views
Why does coNP⊆NP∖P imply that the polynomial hierarchy collapses?
I was looking for some information on 1-in-3 SAT and came across this paper, last updated 9 days ago, which claims that the Polynomial Time Hierarchy collapses "to the level above P=NP". That's quite ...
1
vote
1answer
87 views
Reducing 3 SAT to 3 SET PACKING
I'm trying to prove NP-hardness of 3 SET PACKING, which is a following problem: given a family of sets where each set contains 3 elements, decide whether the family contains k sets that are pairwise ...
3
votes
2answers
59 views
Proving a problem as NP-complete
According to this article,
A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time reduced to current problem X. The problem also needs ...
0
votes
1answer
127 views
Proving NP completeness of maximal length path
I have this question to answer:
For each node i in an undirected network $G = (N,E)$, let $N(i) = \{j \in N : \{i, j\} \in E\}$ denote the set of neighbors of node $i$ and let $c_e\geq0$ denote the ...
3
votes
1answer
53 views
Quantum vs classic in NP-hard problems
Is there any quantum algorithm (algorithm for quantum computers) for any NP-hard problem that has better runtime than the best known classic algorithm's runtime?
3
votes
2answers
165 views
Why isn't the Generalized Super Mario Bros. obviously in NP?
It is shown in the paper: "Classic Nintendo Games are (Computationally) Hard" by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta that the Generalized Super Mario Bros. (SMB, for short) ...
1
vote
1answer
59 views
Reduction from NP-complete problem to unknown complexity problem and vice-versa
Suppose I have two problems: $B$, which is NP-complete, and $A$, of unknown complexity.
Question:
If I show that $B \le A$ I can state that $A$ is also NP-complete because the two required ...
2
votes
0answers
30 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.
...
