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
20 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
20 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
0answers
26 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
40 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 ...
-1
votes
0answers
42 views

Reduction of SAT to Vertex Cover

I'm trying to understand how to reduce the below circuit-satisfiability problem into a vertex-cover problem. That is, show the resulting vertex cover graph and the number of vertices to select. Anyone ...
0
votes
3answers
79 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
33 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
47 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
92 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
50 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
46 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
30 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
57 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
59 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
143 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
67 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
73 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
64 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
32 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
31 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
17 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
48 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
276 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
259 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
97 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
68 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
77 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
67 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
60 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
65 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
42 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
54 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
34 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
100 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
87 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 ...
4
votes
1answer
24 views

MIS complexity in cubic triangle-free graphs

The question Complexity of Independent Set on Triangle-Free Planar Cubic Graphs asks for the complexity of the independent set problem in triangle-free planar cubic graphs. In the statement of the ...
1
vote
1answer
60 views

How to build the Reduction from Hamiltonian Cycle problem to Subgraph isomorphism? [duplicate]

I'm trying to prove that the Subgraph isomorphism problem is NPC using the Hamiltonian Cycle problem. Unfortunately I feel (or don't understand) that the solution is "empty" and doesn't explain the ...
1
vote
1answer
39 views

L closed under logspace reduction

Given two languages $A$ and $B$ I have been asked to show that, if $B \in L$ and we have a logspace reduction $f$ from $A$ to $B$ then $A \in L$. I read the proof that $L$ is closed under logspace ...
5
votes
0answers
48 views

Turing reductions by NX ∩ coNX and binary relation problems

Let $A$ be a non-deterministic algorithm computing a binary relation between an input string and possible output strings. Let NX be a (potentially non-deterministic) complexity class. What is a good ...
2
votes
1answer
56 views

How exactly does a Max 2 Sat reduce to a 3 Sat?

I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if you see the article, I'm not able to understand why, after ...
4
votes
1answer
329 views

EQtm is not mapping reducible to its complement

This is a problem from Sipser's book (marked with an asterisk). $EQ_{TM} = \{(\langle M \rangle, \langle N \rangle)$ where $M$ and $N$ are Turing machines and $L(M) = L(N)\}$ We know that neither ...
3
votes
1answer
54 views

Is the following language recursively enumerable?

Let $L =\{ <M> | $ the amount of words $w\in\Sigma^*$ that $M$ does not halt on is finite $\}$. I would like to prove that $L\notin RE$. I can show that $\overline{L}\notin RE $ that is ...