Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science
Questions tagged [np-complete]
676 questions
0
votes
3 answers
is there a real-life example to elaborate NP-complete?
In computational complexity theory, a problem is NP-complete when it can be solved by a restricted class of brute force search algorithms and it can be used to simulate any other problem with a similar algorithm.
is there a real-life example to…
Jay
- 511
- 2
- 7
0
votes
1 answer
Polynomial-Time Reduction, "at least as hard as", 3-COLOR and 4-COLOR
The theme is NP-Completeness, I find it hard to grasp the concept of "$A$ is at least as hard as $B$". Why does this mean that we have to reduce $B$ to $A$ and not $A$ to $B$? For me the latter makes a lot more sense. If it takes $n$ steps to solve…
Clash
- 1,401
0
votes
1 answer
If a NP-complete problem is not in P, then all NP-complete problems are not in P?
It is clear to me that if a NP-Hard problem is solvable in P, then all NP-Hard problem (which include NP-Complete problems) are solvable in P.
But, is it also the case that if a NP-Complete problem is ever proven to be not solvable in P, then all…
0
votes
1 answer
Reducing 3 SAT to max 2 SAT
In the reduction done here, you take one clause $d = a \cup b\cup c$, and make 10 clauses
$a, b, c, d, a \cup \neg d, b \cup \neg d, c \cup \neg d, \neg a \cup \neg b, \neg b \cup \neg c, \neg a \cup \neg c$
Then in the case of all $a,b,c = 0$ leads…
sma
- 336
0
votes
1 answer
Reducing Subset-Sum to Scheduling with start time.
Given a set of $n$ jobs with processing time $t_i$, release time $r_i$, and deadline $d_i$, can we schedule all $K$ number of jobs ($0 \le K$)on a single machine. Reduce SubsetSum to Schedule. The solution goes as Given an instance of SUBSET-SUM…
ElleryL
- 1,583
0
votes
1 answer
Show formally that problem is NP-Complete
City has $1, ..., n$ citizens. Citizen $c_{i}$ has $v_{i}$ number of votes and each citizen's vote can be bought for certain price $p_{i}$. Election can be won by getting at least half of the votes. Given $F$ funds and knowing that each not bribed…
0
votes
0 answers
Hamiltonian Path with restrictions
I'm trying to solve the hamiltonian path problem but with restrictions.
What sort of restrictions? Each vertex has a value, and if the value is i, than I want the hemiltonian path to include this vertex on it's i'th place on the path.
For example, I…
Tal Yitzhak
- 43
0
votes
1 answer
NPC: Reduction of VC to 2VC
A professor gave us this problem, which I could not solve:
Reduce VC to 2VC. (Prove that 2VC is NPC)
Definition: 2VC gets G, and K, and returns true if there are 2 different VC in size K in G. (In the same way that double clique finds 2 clicks in…
Amit
- 153
0
votes
1 answer
Is this coverage problem NP-hard?
Consider a set of K sensors which have a sensing disc of fixed diameter. We can put sensors on any point within the area. We are interested to deploy all these sensors in an area $A$, such that the total covered area is maximized. Can we say this…
ladan
- 73
0
votes
1 answer
If an NP-hard problem is a special case of problem A, can we conclude problem A is NP-hard?
Problem B is a special case of Problem A (problem A has additional variables $v_{additional}$ in comparison to problem B). This means for a specific value of $v_{additional}$, problem A is exactly the same as problem B. We know problem B is NP-hard.…
ladan
- 73
0
votes
1 answer
NP reductions; if $Q_1$ reduces to $Q_2$, what can we infer about $Q_2$ given what we know about $Q_1$?
I am trying to grasp this concept of reductions, which has surfaced during my study of NP-completeness.
So, my textbook notes that "if $Q_1$ reduces to $Q_2$, then $Q_1$ is at least as easy as $Q_2$." First of all, this claim seems counterintuitive.…
kanker7
- 275
0
votes
0 answers
NP inference explanation
I've been taking a look at the following question and came up with some answers but I'm wondering if there's more to it.
The Question is as follows:
Assume that there are proofs for the following four statments. Can you infer anything about A, B, C,…
Java Beans
- 33
0
votes
1 answer
Is there any significant consequence if P does not equal NP-complete?
I hear a lot on these forums about how if P=NP-complete how our lives would be better, is there any significant consequence if we found P to be not equal to NP-Complete?
jaysonpowers
- 475
0
votes
0 answers
Proving NP-completeness
I want to prove the following problem is NP-Complete:
$$\text{Given a weighted graph } G=(V,E), \text{ a vertex } v\in V \text{ and a number } K $$
The answer is YES if there exist a path of weight $K$, starting from $v$ , goes through all vertices…
Genadi
- 381
-1
votes
1 answer
Shortest Common String Problem is NP
Does anyone know how to prove that Shortest Common String Problem is NP?
I can provide a proof that it is NP-hard but I don't know how to prove SCSS in NP.
