Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science
Questions tagged [np-complete]
676 questions
1
vote
1 answer
Is the n-Queens problem only np-complete for the task of finding all setups or also for finding any solution?
I have read on Wikipedia that the n-Queens problem is NP-complete when it comes to finding all possible solution implies it that finding one possible solution is also NP-complete?
baxbear
- 233
1
vote
0 answers
How to prove a submodular maximization problem is NP-hard
We know that a submodular maximization problem of the form
$$
\mathcal{P}: \,\, \mathop {\max }\limits_S f\left( S \right)
$$
where $f(S)$ is a submodular set function, is NP-hard (Claim 1).
This claim can be proven by reduction from a well-known…
Junny
- 11
1
vote
0 answers
Can't understand this statement
I was reading some bachelor thesis and it mentioned reducing the hitting set problem to the set cover problem. However I am unable to understand the last line in the referenced paragraph, I would really appreciate if someone can help clarify it.…
1
vote
1 answer
How to prove that subset-problem is NP-complete
Let's imagine that we have a finite set S and finite subsets S_1, S_2,.....S_k. We also have 2 numbers: lower_i and higher_i for each subset. We want to answer: Is there a subset $$T \subseteq S $$ such that for each i runs: $$lower_i <= |T \cap…
Jonny
- 31
1
vote
1 answer
Approaches for solving P vs NP problem
I want to get acquainted with approaches made to solve P vs NP problem.
1) What is already achieved in solving the P vs NP problem?
2) What articles are most cited/famous in that field? Please, provide links for them.
3) How one can divide existing…
Sega
1
vote
1 answer
Complement of SEMIPRIME is in NP
The decision version of SEMIPRIME asks if a positive integer n can be factored into 2 primes.
The complement of SEMIPRIME asks if n cannot be factored into 2 primes.
My understanding is that the complement of SEMIPRIME is in NP because a certificate…
user137481
- 2,605
1
vote
0 answers
If a problem in $P$ can be rewritten to $NPC$, why can this $NPC$ problem not be solved in polynomial time?
According to multiple definitions and my math professor, problems in $NP$ can be rewritten to a problem in $NPC$, including problems in $P$. Why can I solve a $P$ problem in polynomial time, but can't solve the $NPC$ version in polynomial time. Are…
0
votes
2 answers
P and NP and NP-complete and NP-hard in simple terms
I'm trying to wrap my head around what all these terms mean and here is my understanding so far. I'm hoping you can improve my understanding of what these terms mean.
P is the set of all problems which can be efficiently solved.
NP is the set of all…
Ogen
- 2,255
- 8
- 31
- 44
0
votes
1 answer
should we try to solve problem in np class
Good afternoon everyone;
I am having difficulties to discriminate between NP and NP completeness. For instance, we know that a problem is in NP class should we try to find a algorithmic solution for this problem?
Regards,
Can
- 171
0
votes
1 answer
Proof of: if L is in NP then its complement is coNP-Complete
I have trouble understanding why we need to construct a function to do the following proof and how the function shows that $A \leq_{p} L$:
Claim: If L $\epsilon$ NP then $\overline{L}$ is coNP-complete.
Proof: Consider any A $\in$ coNP. We know…
user2193268
- 303
- 4
- 11
0
votes
1 answer
proving specific language is a NP-Complete
I got this question and I'd happy for help.
$Satn^7$ is a language that containes all the CNF formula (P) which fulfill the next rule: There is a least $n^7$ satisfactory assignments, when n is the number of the variable in P.
I need to prove that…
Eyal
- 3
0
votes
1 answer
How we reduce NP problems?
Assume that P1, P2,..., Pn are NP-class problems. PP1 and PP2 are unknown problems (i.e., we don't know whether they belong to the P or NP classes). If "P1, P2,...., Pn" problems can be reduced to PP1 in polynomial time, then PP1 can be reduced to…
0
votes
1 answer
NP-complete decision problems
Are the following statements true or false? Why? What could I use to prove these statements?
A decision problem is NP-complete if and only if there is a polynomial-time
reduction from SAT to it.
A decision problem is NP-hard if and only if there…
John
- 1
0
votes
1 answer
P-NP for decision problems
The final quiz problem asked whether the statement
For decision problems L1, L2 in NP, if P is not NP, L1 is at least as hard as L2, and L2 is at least as hard as L1, then L1 and L2 are NP-complete
is true or false. In fact, it seemed to me even…
rasul_rza24
- 81
0
votes
1 answer
What commands would a P=NP algorithm consist of?
Taking the example of boolean satisfiability problem. We might have something like:
$$(a \lor b \lor c \lor d)\land (a \lor d \lor e) \land (f \lor b \lor g)$$
The statement is that there is no algorithm acting on a general input that would give the…
zooby
- 4,343