Linked Questions

-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 < ...
user6818's user avatar
  • 1,135
-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 ...
Roger Bresnan's user avatar
0 votes
1 answer
909 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: ...
user avatar
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 ...
Fredrik's user avatar
3 votes
2 answers
439 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 ...
Olórin's user avatar
  • 859
2 votes
1 answer
253 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 ...
Mark's user avatar
  • 23
1 vote
0 answers
222 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|\...
azureai's user avatar
  • 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?
nick's user avatar
  • 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?
Mina Akram's user avatar
0 votes
1 answer
45 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 \;:\; (\...
eatfood's user avatar
  • 175
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} ...
RandomGuy's user avatar
  • 111
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 ...
Sean Kelly's user avatar
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) ...
eternalmothra's user avatar
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 ...
Anonymous's user avatar
  • 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 ...
user5507's user avatar
  • 2,191
10 votes
2 answers
6k views

Mapping Reductions to Complement of A$_{TM}$

I have a general question about mapping reductions. I have seen several examples of reducing functions to $A_{TM}$ where $A_{TM} = \{\langle M, w \rangle : \text{ For } M \text{ is a turing machine ...
RageD's user avatar
  • 203
2 votes
2 answers
8k views

Is the language TMs that accept finite languages Turing-recognizable?

I know that $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not decidable (by Rice's theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable? What I ...
advocateofnone's user avatar
8 votes
3 answers
689 views

What is the name of this logistic variant of TSP?

I have a logistic problem that can be seen as a variant of $\text{TSP}$. It is so natural, I'm sure it has been studied in Operations research or something similar. Here's one way of looking at the ...
Juho's user avatar
  • 22.5k
1 vote
1 answer
12k views

Proving a language is not Turing-recognizable by reduction from $D = \{\langle M\rangle \mid M \text{ rejects input }\langle M\rangle\}$

I'm having a really hard time understanding some of these concepts. I've read them over from several different sources and still can't reach the a-ha moment. I need to prove a language $L$ is not ...
Tanner's user avatar
  • 11
7 votes
2 answers
527 views

primitive recursive functional equivalence

Given two primitive recursive functions is it decidable whether or not they are the same function? For example lets take sorting algorithms A, and B which are primitive recursive. While there are many ...
44701's user avatar
  • 459
1 vote
2 answers
4k views

How can one reduce 3-CNF-SAT and k-CNF-SAT to each other?

I am studying for NP problems. To prove k-CNF-SAT is NP-hard, there must exists something that can be reduced to k-CNF-SAT. So what I thought is to reduce 3-CNF-SAT to k-CNF-SAT and reduce k-CNF-SAT ...
proX's user avatar
  • 29
3 votes
2 answers
2k views

Need Help Reducing Subset Sum to Show a Problem is NP-Complete

I want to show that the following problem is NP-Complete: For a set of vectors $v_1,\ldots,v_n \in \mathbb{N}^d$ and an integer $k$, does there exist a subset $S \subseteq \{v_1,\ldots,v_n\}$, such ...
Newb's user avatar
  • 314
5 votes
1 answer
3k views

Showing a problem is NP complete? Reducing CLIQUE to KITE.

I've got an exam next week all about this sort of thing. Ie: Find polynomial certifier for a problem, give a polynomial reduction, prove problem X reduces to Y and etc. The problem is, there doesn't ...
Jay's user avatar
  • 53
2 votes
3 answers
2k views

Prove that finding largest subset of undirected graph that is almost independent is NP-hard

A subset $S$ of vertices in an undirected graph $G$ is called almost independent if at most 100 edges in $G$ have both endpoints in $S$. Prove that finding the size of the largest almost-independent ...
AndroidFish's user avatar
2 votes
3 answers
3k views

Can the edges of a graph be assigned directions such that all nodes in a given subset have in- or outdegree 0, and every other node indegree > 0?

In a directed graph, the indegree of a node is the number of incoming edges and the outdegree is the number of outgoing edges. Show that the following problem is NP-complete. Given an undirected graph ...
kiran's user avatar
  • 37
3 votes
3 answers
358 views

Has anyone seen a NP graph problem like this before?

I have a following graph-based problem: Input: positive integers K and L, undirected graph G I have to choose K vertices from this graph In the path between each pair of chosen K vertices there ...
qalis's user avatar
  • 169
1 vote
2 answers
949 views

How to show the function is not Turing computable?

Having the function: $$f(y) = \begin{cases} \ 1 &\text{if }\forall n \Phi_y(n)=n\lor \Phi_y(n) \!\uparrow\\ \ 0 &\text{otherwise.} \end{cases}$$ By the rule of thumb it ...
TechCrap's user avatar
  • 145
3 votes
2 answers
2k views

Negative simple path NP-Complete

Given a graph $G=(V,E)$, and positive and negative edge weights, negative path problem asks if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$ My approach was to ...
Kaan Yolsever's user avatar
3 votes
1 answer
2k views

Is regularity of the language accepted by a given Turing machine a semi-decidable property?

Given is the definition of a general problem: $\{ \langle M, S\rangle \mid M \text{ is a } TM, L_M \in S\}$. In words: Given a TM M, does M decide a language that is an element of the given set of ...
Ad Fundum's user avatar
  • 229
1 vote
1 answer
2k views

Proving a language is neither Recursively Enumerable nor co-Recursively Enumerable

$$L = \{ \langle M \rangle \mid \text{\(M\) is a Turing Machine and \(|L(M)| = 1\)} \}$$ I have to prove that this is not R.E. and not co-R.E. I know how to approach these kind of problems. For $\...
parsimony's user avatar
4 votes
1 answer
1k views

Is it possible to mapping reduce either of these languages to the other?

I have the following two languages, which are languages of TM descriptions: $$INFINITE = \{ \langle M \rangle | \mbox{M is a TM and L(M) is infinite} \}$$ $$A_{ALL} = \{ \langle M \rangle | \mbox{M ...
templatetypedef's user avatar
2 votes
1 answer
761 views

How to find subset of vectors whose sum has certain characteristics

Let's say you have list of $n$ vectors with entries from $\{0,1,x\}$ and $x$ is > $n$: $$ \begin{align*} L_0 &= [1,0,x] \\ L_1 &= [1,1,1] \\ L_2 &= [1,0,0] \\ L_3 &= [x,1,0] \\ L_4 &...
Akim Akimov's user avatar
8 votes
1 answer
606 views

Relaxed Bin Packing Problem

The problem I have is like this bin packing problem, but instead I have $n$ bins and a collection of items with discrete masses. I need to put at least $m$ kg of stuff in each bin. Is there an ...
Lucas's user avatar
  • 201
2 votes
2 answers
740 views

Check if K-Sum Variation is NP-Complete

Problem Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such that the sum is equal to $s$. Question This problem came from evaluating some scheduling algorithms that I am ...
tkellehe's user avatar
  • 157
5 votes
1 answer
198 views

Prove that "Finishing the degree in three years" problem is NP-Complete

I was asked in an interview the following question: We'll define the "Finishing the degree in three years" problem in the following manner: Given a list of courses $C=\{c_1, c_2,\ldots, c_n\}$, ...
gusfring's user avatar
0 votes
1 answer
1k views

Showing party invitation problem is np-complete

Suppose you and your $k - 1$ housemates decide to throw a party. Each housemate $i$ gives you a list $P_i$ of people she would like to have invited to the party. Depending on how much you like ...
Kaan Yolsever's user avatar
0 votes
1 answer
495 views

NP Completeness of 3-SAT problem [closed]

I have started reading on algorithmic complexity for my thesis work. Already have studied on Polynomial time reducibility, NP-Complete, NP-Hard. Now trying to prove NP completeness of some of the ...
vessilli's user avatar
1 vote
1 answer
607 views

Is the set of Gödel numbers of computable constant functions recursively enumerable?

I've been working on the following exercise: $S = \{ x | f_x \text{ is constant} \}$. Is $S$ recursively enumerable? Here, $fx$ is the function computed by the $\text{x-th TM}$. So it is a ...
PALEN's user avatar
  • 317
1 vote
1 answer
459 views

DFA accepts common strings, reduction to NPcomplete

$B=\{\left<M_1,M_2,...,M_k\right>\text{ : Each $M_i$ is a DFA and all of the $M_i$ accept some common string.} \}$ I'm trying to show that B is NP-complete. I know I have to reduce it to ...
Indigo's user avatar
  • 165
0 votes
1 answer
714 views

Proof NP-Complete for Single machine Job Scheduling Problem specific version

Problem: given a set of n tasks with execution time Ti, due date Di, and a profit Vi (given only if is enden before due date), is there a task schedule that returns a total profit greater or equal ...
Tomas Botalla's user avatar
4 votes
1 answer
150 views

NP hardness through Restriction

Let's say I have a decision problem $P$ on graphs for which I know that it is NP-hard on graphs with maximum degree $d$. Does this then imply that it is NP-hard on $d$-regular graphs? Although it ...
Matt's user avatar
  • 43
0 votes
0 answers
737 views

How to use SAT reductions to prove set-splitting problem is NP-Complete?

I am having a difficulty proving that the set splitting problem is NP-complete using SAT. Suppose S = {1,2,3,4} and C is a collection of subsets of S, say C1 = {1,2}, C2 = {3,4}, C3 = {1,3,4}. Each ...
coder123's user avatar
  • 165
-1 votes
2 answers
154 views

Graph Isomorphism variant

Question: Given 2 undirected graphs $G_1$, $G_2$, the problem whether exists a subgraph H1 of G1 which is isomorphic to a subgraph $H_2$ of $G_2$. What is the lowest complexity class for this problem: ...
jreing's user avatar
  • 205
-1 votes
1 answer
252 views

Given an arbitrary language, how does one go about proving that it is recursive or otherwise?

I am having problems knowing how to prove a language is recursive or not. Is there a particular general strategy is used for such a problem, or possibly some principle which is often used? Thanks ...
thesilverscientist's user avatar
-2 votes
2 answers
364 views

Find a simple path through a graph, vising as many vertices in Z as possible

Goal: Find a simple path in G, that visits the maximum number of vertices in Z and prove it is NP-complete. G = (V , E) Z is a subset of V How would I go about doing this?
electrumguy's user avatar
0 votes
3 answers
353 views

Show that finding a minimum-weight subgraph that includes all marked nodes is NP-hard

We've been given a weighted graph with marked nodes. We want to make a minimum-weight subtree from this graph that contains all marked nodes. I want to show that this problem is NP-hard. Is there any ...
user3070752's user avatar
2 votes
1 answer
263 views

Is the search for a k-Hamiltonian Path NP-hard?

A $k$-Hamiltonian Path is an Hamiltonian Path where each node (but the last $k$ nodes on the path) is connected to his $k$ successors, and the last $k$ nodes are connected to all of their successors. ...
Luca's user avatar
  • 133
-1 votes
1 answer
516 views

Reducing from Hamiltonian Cycle problem to the Graph Wheel problem cannot be proved vice versa [closed]

I saw a proof by Saeed Amiri, We will add one extra vertex v to the graph G and we make new graph G′, such that v is connected to the all other vertices of G. G has a Hamiltonian cycle if and only if ...
Ronnie's user avatar
  • 1
0 votes
1 answer
392 views

Subset-sum variation, multiple sums

Subset-sum problem is NP-complete. I presume so is the problem of determining, given a positive integer $p$, whether in a set of positive integers $\{x_1,x_2,...,x_n\}$ there is a subset which sums to ...
Jules's user avatar
  • 337
1 vote
1 answer
296 views

Variation of the Partition Problem

Is the variation of partition problem where instead the sum of the sets only be equal to a value $B$, they could also differ by two ( i.e., the sum of one set could be $B-1$ and the other $B+1$ ) ...
Daniel D.'s user avatar

15 30 50 per page