Linked Questions

1 vote
1 answer
184 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 ...
user55567's user avatar
1 vote
1 answer
180 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 ...
codetumbler's user avatar
2 votes
0 answers
230 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 ...
bakedturtle's user avatar
1 vote
0 answers
214 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 ...
Ponsietta's user avatar
  • 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 ...
djechlin's user avatar
  • 497
4 votes
0 answers
135 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 ...
Dong  Deng's user avatar
2 votes
1 answer
100 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 ...
ytj's user avatar
  • 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 $$...
Ali Shakiba's user avatar
-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$ ...
Eric's user avatar
  • 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 ...
labxq's user avatar
  • 33
2 votes
1 answer
107 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{ ...
defaultjay's user avatar
-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$ ...
Kep Ion's user avatar
0 votes
0 answers
101 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 ...
lostCS's user avatar
  • 1
0 votes
0 answers
92 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 ...
user90210's user avatar
0 votes
2 answers
64 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 ...
Mike's user avatar
  • 33

15 30 50 per page