Linked Questions
85 questions linked to/from What are common techniques for reducing problems to each other?
-1
votes
1
answer
7k
views
How to reduce bin-packing problems? [duplicate]
This is my first time with reductions and I can't figure out how to do them. I have read the few standard examples that are given in the standard books.
For example, given $n$ numbers $\{ 0 < ...
- 1,125
-2
votes
1
answer
3k
views
Prove PSPACE is closed under complement? [duplicate]
How would you prove PSPACE is closed under complement? So far, my thought process is that we can create an algorithm to show that P is closed under complement. I'm struggling with how I can connect ...
0
votes
1
answer
886
views
Satisfying assignments, twice-3SAT NP complete [duplicate]
I wanted to solve the following problem about 3SAT . The question is
1. to show if the problem is NP-complete and
2. whether the problem has two different satisfying assignments.
"TWICE-3SAT Input: ...
user28838
0
votes
0
answers
696
views
Reduce Subset Sum to a modified knapsack problem [duplicate]
The problem looks a bit like the knapsack problem, but here the objects placed in the sack are unique and it is allowed to overflow the sack. The main goal is to see if it is possible to fill all of ...
- 1
3
votes
2
answers
431
views
Can someone provide a trivial example to the "reduction" procedure used to prove hardness? [duplicate]
I cannot comprehend how you can prove hardness between two NP complete problems.
For example, let X be a NP hard problem, I want to prove Y is also NP hard.
I can do this by reducing X to Y, if Y is ...
- 859
2
votes
1
answer
250
views
Proving problem NP-completeness [duplicate]
I am studying computational complexity and i am trying to solve this problem.
We are given a (non-bipartite) complete graph:
G = (V, W, E)
where the vertices can be divided in two classes V and W ...
- 23
1
vote
0
answers
208
views
Proving reducibility of a language to another language [duplicate]
I am self-studying formal languages and want to solve an example problem. Given formal languages $A,B\subset\Sigma^*$ over an alphabet $\Sigma=\{a,b,c\}$ with
$$A=\{\omega\in\Sigma^*\vert\left|\...
- 111
-3
votes
1
answer
104
views
Complexity if special case of SAT [duplicate]
I have the following problem: How to show that the special case of SAT, in which each clause has either exactly two literals or at most one negative literal, is NP-complete?
- 11
0
votes
0
answers
76
views
How to prove QUADPROG is NP-hard using 3COLOR? [duplicate]
I am given a task to prove using 3COLOR that Quadratic Programming is NP-hard. Does anyone have a clue on how this is meant to be done?
0
votes
0
answers
45
views
How can I determine whether a problem is NP-Hard [duplicate]
So I have a problem, I'm highly confident that it's NP-Hard, though I'm not really sure how I can convince my self this is the case?
Suppose I have different groups of people m in a list
M= {m1, m2}
...
- 111
0
votes
1
answer
44
views
Prove that $L = \{a^i \;:\; (\exists x \in \mathrm{Lang}(M_i))\;[ xx \notin \mathrm{Lang}(M_i) ] \}$ not recursively enumerable [duplicate]
Past year paper question:
Let $M_i$ denote the Turing machine with code $i$ using the alphabet $\Sigma=\{a,b\}$.
Show that the following language is not recursively enumerable:
$L = \{a^i \;:\; (\...
- 175
0
votes
0
answers
33
views
Proving NP-Complete Help [duplicate]
I am trying to prove that the problem of having a person at the minimum x number of intersections to be able to see each street is NP-Complete. I think that the street problem is very similar to the ...
0
votes
0
answers
25
views
General methods for polynomial reductions? [duplicate]
Let's say you want to show $A \leq_{p} B$ (this is usually in the context of showing $B$ is NP-complete, but I'm just asking about the reductions. We are specifically looking at polynomial (Karp) ...
- 249
37
votes
2
answers
18k
views
How do I construct reductions between problems to prove a problem is NP-complete?
I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How ...
- 371
45
votes
2
answers
21k
views
How to show that a function is not computable? How to show a language is not computably enumerable?
I know that there exists a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
- 2,181