Questions about finding mappings between problems that allow solving one problem using a solution of another one.

learn more… | top users | synonyms

0
votes
1answer
101 views

Decidability of the TM's computing a none empty subset of total functions

I have this HW problem: Let $F$ be the set of computable total functions, and let $\emptyset\subsetneq S\subseteq F$. Denote $$L_S=\{ \langle M \rangle | M \text{ is a TM that computes a function ...
-4
votes
0answers
23 views

Complexity of three subset sum variants [closed]

What is the complexity class of following three problems? (1) Given $n$ integers and another integer $c$ with promise that every subset sum is unique is there a subset that sums to $c$? (2) Given ...
1
vote
0answers
40 views

Reducibility of finding Eulerian Path to Linear Programming

Consider any arbitrary directed, acyclic graph; how can we formulate the problem of finding a particular Eulerian path as a linear programming problem? It seems like there should be a relatively ...
3
votes
1answer
57 views

Undecidability of REGULAR_TM (Detail within Proof)

I'm reading through Sipser's Intro to the Theory of Computation for a class, and I'm having trouble understanding one of the examples in the book. The example shows how $REGULAR_{TM}$, defined as the ...
3
votes
1answer
28 views

Is it true that independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP?

I was reading a paper and I came to the following : "Since independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP (see [19]) for any fixed $\epsilon> 0$, the ..." where [19] is the ...
0
votes
1answer
27 views

What do we mean when we say an edge (u,v) connects some component to other component in forest G = (V,A)

Let H = (V,E) be a connected, undirected graph. Let A be a subset of E. Let C = (W , F) be a connected component (tree) in the forest G = (V,A). Let (u,v) be an edge connecting C to some other ...
1
vote
1answer
49 views

Turing NP complete but not Karp NP complete?

Is there some examples of candidate problems that have Turing reduction from SAT but no known Karp reduction? Conversely is there some examples of candidate problems that have Turing reduction to SAT ...
0
votes
0answers
18 views

Particle locating/collision prediction in bounded (two-dimensional) environments

I believe that many physics engines, particle simulators, and even video games use discrete-event simulation to determine where a particle or object is at any moment, and the direction in which it is ...
0
votes
1answer
54 views

Implications of Halting Problem being unsolvable?

I came across a confusing situation when reducing the Halting Problem (HP) to the Blank Tape Accepting Problem (BP). We know that since HP can be reduced to BP, BP is decidable $\implies$ HP is ...
1
vote
1answer
34 views

Prove Undecidability Without Using Rice's Theorem

Show that checking if a TM accepts some input string of length greater than some constant $k$ is undecidable. Here the constant $k$ is publicly known. I tried solving this problem by trying to reduce ...
0
votes
1answer
58 views

Satisfiability 2 CNF-SAT to 3 CNF-SAT transformation/reduction

This Reduction is trying to prove that 2CNF-SAT is also NP-Complete, after proving 3CNF-SAT is NP-Complete. If we had a reduction that given an instance of 2CNF-SAT with k clauses over 'i' number of ...
0
votes
1answer
49 views

show that special case of NP-complete problem is also NP-complete?

I want to show that a problem is NP-hard by reducing a known NP-complete problem to it. However, I will have to use a special case of the NP-complete problem for the reduction to work. I'm pretty sure ...
1
vote
0answers
26 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 a1,a2...,an Question: Can the list be partitioned into 2 parts, A1 & A2 such that the sum of each part is ...
2
votes
0answers
32 views

Minimum cost edge disjoint paths - NP hard?

I've been stuck on this problem for a while now. Here it is: The Network Reliability Problem (NRP) is defined as follows: Given an undirected graph with $n$ vertices $v_{1}, \dots, v_{n}$, a ...
3
votes
1answer
41 views

Need help in a question regarding polynomial oracle reductions

Prove the following: If there is a polynomial oracle reduction from $S1$ to $S2$: a. If $S2\in\ P$ so $S1\in\ P$ b. If $S2\notin\ P$ so $S1\notin\ P$ The way I see it - If there is a polynomial ...
0
votes
3answers
80 views

Size of instance after reduction

A decision problem $C$ is $NP$-complete if $C$ is in $NP$, and every problem in $NP$ is reducible to $C$ in polynomial time. Reduction means transforming an instance of one problem $A$ to an instance ...
0
votes
1answer
36 views

How is the formal definition of NP-hard equivalent to this colloquial one?

Wikipedia informally describes NP-hard problems as "at least as hard as the hardest problems in NP". It then states the formal definition: "a problem H is NP-hard when every problem L in NP can be ...
3
votes
1answer
48 views

Decidability of equivalence problem with limit

I already know, that the language $$L_0 = \{m \mid \text{the Turing machine $m$ does not stop on an empty tape}\}$$ is not decidable. If I want to know, if $$EQ = \{\langle m, n \rangle \mid L(m) = ...
1
vote
1answer
93 views

Is this a well-known NP-hard problem?

Let $R = \{1, \ldots, n\}$ and $S = \{S_1, \ldots, S_m\}$ a collection of subsets of $R$ such that $R = \bigcup_{i = 1}^m S_i$ and, for $n > 3$, $$3 \leq \vert S_i \vert \leq 4 \, , \enspace i \in ...
0
votes
0answers
51 views

Max Flow / Linear Programming Reduction Variant

While studying max flow / LP, I came across a couple of reduction problems that gave me a bit of pause: Here are two variants of the standard Maximum Flow problem. Show that both of them can be ...
0
votes
0answers
28 views

Satisfying two constraint with an oracle for satisfying one

Given an oracle to solve the knapsack feasibility problem: $$a^Tx=b, \ x \in \mathbb{N}^n $$ How can one solve in polynominal time the problem of satisfying two constraints at the same time?
2
votes
1answer
47 views

Is the unweighted vertex cover problem equivalent to its weighted version?

Consider the unweighted and weighted versions of the vertex cover problem (UVC and WVC for short, respectively). As UVC is a special case of WVC, is it true that $$\text{UVC} \leq_\mathrm{m} ...
0
votes
1answer
31 views

Log reduce PATH to DISTANCE-PATH

An instance of PATH is given by where G is a directed graph, s and t are nodes in the graph, it's a true instance if G has a path from s to t. DISTANCE-PATH is similar, but with an extra requirement ...
1
vote
1answer
58 views

Reduce set partition search to decision?

I'm a little lost and don't know how to approach this problem. Show the partition search problem can be poly-time reduced to the partition decision problem, the partition decision problem takes ...
2
votes
1answer
60 views

Packing sets to maximize overlap

We are given a set of $m$ elements $\{e_1,...,e_m\}$ that form our universe $\mathcal{U}$. Each element of our universe is further associated with a positive weight $w(e_j)$ with $j\in \{1,...m\}$. We ...
0
votes
0answers
146 views

Trying to show if two languages are recognizable or not

I have two languages that I am trying to prove are recognizable or not: Let L1 = {<\M, w> : M is a Turing machine that accepts string w and does not accept string ε}. Is L1 recognizable? Prove ...
1
vote
2answers
71 views

What does it mean to be Turing reducible?

I'm confused about what it means to be Turing reducible. I thought I understood what it meant, but apparently not. $A \leq B $ Means that A is Turing reducible to B. This means that given an oracle ...
1
vote
1answer
83 views

Reducing co3SAT to UNIQUE-SAT

I am having trouble with this problem: Let N3SAT denote the non-satisfiability problem for 3CNF’s. Show that $N3SAT\leq_p UNQ$ where in UNQ, given a CNF φ we want to know whether there is a unique ...
0
votes
2answers
66 views

Polynomially reducing NP-Complete problem clarification

I am having trouble solving the following question. I am given a following problem X: Given a graph G, we want to know whether there is an edge e in G such that G − e is 3-colorable. I want to show ...
1
vote
1answer
32 views

Does a reduction with $\infty$ work?

Lately, I saw an NP-complete proof that involves creating an instance of a problem using $\infty$. Is this a polynomial-time reduction? More precisely, let a problem $\Pi$ has an instance $I=(n, A, ...
0
votes
1answer
40 views

Reduce knapsack to problem with {0,1}-Matrix

I'm looking for a problem, where i can reduce the knapsack feasibility problem: $$a^Tx=b,\ \textbf{with} \ a\in \mathbb{N}^n,b \in \mathbb{N}, x \in \{0,1\}^n$$ to a problem, where i have a matrix ...
1
vote
1answer
32 views

Reduction variation for the q-coloring problem

I'm trying to prove that $q$-COL $\leq^P_m q$-COL$_{2q-1}$, where $q$-COL$_{2q-1}$ is the restriction of the q-coloring problem to graphs of maximum degree $2q-1$. Now, it seems fairly obvious "if you ...
3
votes
1answer
28 views

Euler graph k-coloring (np-completeness proof)

I've been studying np-completeness proofs by reduction, and was wondering whether my approach to the following problem is viable. Define an Euler graph as a graph that 1) is connected, and 2) has ...
1
vote
2answers
56 views

Reduction between two decision problems

We are given two decision problems: $Q_1\colon I_1\to\{0,1\}$ and $Q_2\colon I_2\to\{0,1\}$. By definition, if there exists a function $f\colon I_1\to I_2$ such that for each $x\in I_1$ we have ...
0
votes
2answers
302 views

Showing that 3-colorable is NP-complete

Just as a background, 3-colorable problem is as follows: Given a graph $G = (V, E)$, is it possible to color the vertices using just 3 colors such that no neighboring vertices have the same color? ...
3
votes
1answer
266 views

Show that the Halting problem is reducible to its complement

HALT$_{TM}$ is the set of all machine-input pairs $<M,w> $ where $M$ halts on input $w$ The complement of HALT$_{TM}$ is the set of all machine-input pairs $<M,w> $ where $M$ ...
6
votes
1answer
105 views

NP-complete reduction proof — graph problem

While studying proofs of NP-completeness via reduction, I saw a seemingly challenging problem: You are given some undirected graph $G = (V, E)$, along with a set $S$ which consists of 0 or more pairs ...
0
votes
1answer
70 views

NP-completeness proof via reduction

I'm aware that 0-1 integer programming problem is NP-complete, where the problem is stated as: Given some integer matrix A and some integer vector b, determine whether there exists a vector x ...
1
vote
1answer
89 views

CNF-SAT reduction problem variant

I'm aware of the Cook-Levin theorem. I've also seen how to reduce SAT to 3-CNF SAT to show that the latter is also NP-Complete. The following problem is a variant, though, and I'm not sure how to ...
1
vote
1answer
70 views

Is there a logspace version of the reduction used in Cook-Levin?

The proof (one of the standard ones, anyway) for Cook-Levin uses snapshots. E.g., see Cook-Levin proof (end of page 2, early page 3) Now, $z_i$ ( where $z_i$ describes a snapshot of the machine ) ...
0
votes
0answers
73 views

A version of the longest simple cycle problem - NP-completeness reduction proof

I've been learning about proving NP-completeness via reduction, and came across the following problem: Prove via reduction the following: whether a graph $G = (V, E)$ contains a simple cycle using ...
1
vote
0answers
27 views

Filling in the holes of a computable function for reduction

As part of a reduction I am trying to come up with a computable function that will fill in the holes of another function. Suppose $A$ is the set of all $n$ such that $\Phi(x,n)$ halts for all $x \in ...
0
votes
1answer
78 views

ETM Undecidability

I'm having trouble convincing myself of the proof for the following theorem: ETM = { <M> | M is a TM and L(M) = ∅} is undecidable. I think I understand ...
1
vote
1answer
43 views

Proof that the set of all universal CFGs is co-RE complete

Let $\Sigma^*\text{CFL} = \{G \mid G \text{ is a CFG; } L(G) = \Sigma_G^*\}$. Enumerate the r.e. sets by $W_n$. Let $\text{EMPTY}= \{ n \mid W_n=\emptyset\}$. On page 4 of these lecture notes, to ...
0
votes
1answer
56 views

Select a subset of the columns in $3\times n$ matrix, is it NP-hard?

I want to know if this problem is NP-hard? The problem: Given a non-negative integer-valued matrix of size $3\times n$ of the form $$ \begin{bmatrix} a_1 & \ldots & a_n\\ b_1 & \ldots ...
3
votes
1answer
78 views

Is the NP-hardness Proof with One Way Implication Correct and Why?

A problem $\Pi$ is NP-hard if I can prove this: a known NP-hard problem $\Pi'$ reduces to $\Pi$ in polynomial time; and $f(x) \in \Pi\iff$ $x \in \Pi'$. If I can show only one way implication, ...
1
vote
1answer
20 views

Can I change the input of my reductionduring the proof?

To prove that a problem $\Pi_2$ is NP-hard one has to: select a known NP-hard problem $\Pi_1$; from an arbitrary instance of $\Pi_1$, create an instance of $\Pi_2$ in polynomial-time; and show ...
-2
votes
1answer
35 views

Undecidability of language [duplicate]

I'm trying to show the language $L=\{\langle M\rangle: M$ is a Turing Machine with runtime $O(n)\}$ is undecidable. I've been trying to reduce the Halting problem $H_{alt}$ to $L$, but I'm unsure of ...
4
votes
1answer
102 views

Proving a certain superset the halting language is not recursive

Let $\Sigma =\{ 0, 1\}$. Let $val:\Sigma^* \rightarrow \mathbb{N}$ be a function that given a string returns its decimal value, and $L_{halt} = \{\langle M\rangle \langle w\rangle \mid M $ halts on $w ...
2
votes
1answer
92 views

Showing undecidability

I'm given the set $T = \{\langle M, w\rangle : M $ is a Turing Machine that accepts $w^\mathcal R$ whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the ...