1 vote
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 ...
1 vote
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 ...
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 ...
1 vote
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
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
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 ...
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
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
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
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
108 views

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 ...
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 ...