Linked Questions
84 questions linked to/from What are common techniques for reducing problems to each other?
1
vote
1
answer
198
views
Reduction from SAT to shortest cycle?
I have been assigned a homework problem that I cannot figure out:
Prove that SAT has a polynomial-time reduction to the language of undirected non-negative weighted graphs with simple cycle of ...
- 11
1
vote
1
answer
181
views
Reduce Turing Machine
If $T_n = \{ \langle M \rangle \mid M \mbox{ is a Turing machine and } |L(M)| = n\}$ where $n$ is $0,1,2....$
I need to show that if $n \geq 1$, $T_{n+1}$ reduces to $T_n$. I know I need to create a ...
- 21
2
votes
0
answers
231
views
Reducing partition to a partition where sum(partition1) = 3 times sum(partition2)
Given the following NP-complete problem:
PARTITION
Input: A list of positive integers $a_1, a_2, \dots, a_n$.
Question: Can the list be partitioned into $2$ parts, $A_1$ and $A_2$, such ...
- 21
1
vote
0
answers
235
views
Decidability of {(M,w); M terminates on input w and tape of M is empty after computation}
I am currently trying to prove whether the above language is decidable, partially decidable or fully undecidable. I am certain that this language is partially decidable and reducible to the halting ...
- 111
1
vote
0
answers
209
views
Why is it NP-hard to learn a disjunction of k variables as a disjunction of fewer than k log n variables?
I'm looking at the claim in An algorithmic theory of learning: Robust concepts and random projection by R. I. Arriaga and S. Vempala (2006):
Further, it is NP-hard to learn a disjunction of k ...
- 497
4
votes
0
answers
136
views
Complexity of a non-linear knapsack problem
Minimize
$$\sum_{i=1}^{n}\sum_{j=1}^{m_i}w_{i,j}v_{i,j}$$
subject to
$$\sum_{i=1}^{n}\frac{m_i}{m_i+\sum_{j=1}^{m_i}v_{i,j}} < \theta$$
$$v_{i,j}\in\{0,1\}~\forall i,~j$$
where
$w_{i,j}$ and ...
- 61
2
votes
1
answer
103
views
Proving "QUESTION" is NP-Complete by reduction from n-variable 3SAT [duplicate]
I'm struggling with a problem in my theory of computation course that asks us to prove "QUESTION" is NP-complete by reduction from n-variable 3SAT. I've done a number of other similar reductions but I ...
- 21
1
vote
1
answer
96
views
Is this argument wrong "since DOM is special kind of RDOM, then RDOM is NP-hard"?
The domination problem $DOM$ is defined as
$$
DOM = \{ \langle G,k \rangle\ | \ G \text{ has a domination of size } k, K \in \mathbb{N} \},
$$
and the rainbow domination problem $RDOM$ is defined as
$$...
- 371
-3
votes
1
answer
112
views
Showing that M is NP-Complete
An instance of $M$ is a collection of sets $S_1, \dots, S_m$ and a bound $B$. A solution is a set $T$ containing $B$ distinct items, such that
each item in $T$ belongs to some $S_i$, and
each $S_i$ ...
- 43
2
votes
0
answers
129
views
Subset minimizing the cost of a one-sided matching, involving preference orders
We're given a set of items $A=\{1,\dots,m\}$ and a set of people $B=\{1,\dots,n\}$. Each person has a preference ordering for the items in $A$. Each item in $A$ has a specific positive cost for each ...
- 33
2
votes
1
answer
108
views
How to reduce a problem?
I am a bit confused on how to reduce a problem. I'll give an example:
Let's say there is a problem called HALTEMPTY and we know it is undecidable.
$HALTEMPTY_{TM} = \{\langle M\rangle \mid M \text{ ...
- 23
-1
votes
2
answers
105
views
Not sure which NPc problem to use for NPc reduction problem,
I'm attempting to prove a problem is NPc, but I'm not sure which one would be optimal to use,
The problem is:
There are $n$ boars to be caged, and $m$ cages which each cage being able to hold $k$ ...
- 1
0
votes
0
answers
103
views
Proving NP-completeness in relation to putting items in bins
If I can assume that it is NP-complete to determine whether a set of objects can be packed into 2 bins, how can I prove that it is NP-complete to determine whether a set of objects can be packed into ...
- 1
0
votes
0
answers
95
views
how to prove that the property 'doesn't halt for some input' is not semidecidable
I am taking a computer theory class and one of the exercises is to prove that the property "doesn't halt for some input" is not semidecidable. This property is the negation of the property "halts for ...
0
votes
2
answers
65
views
Showing NP-Completeness
I just newly started looking into computational complexity.
Since we don’t know if P = NP, we would like to have a way of saying “This problem is in NP and is really hard unless P = NP.”
This is made ...
- 33