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

learn more… | top users | synonyms

3
votes
1answer
35 views

Shorten Length Reduction

I've stumbled upon this Question: We say that a reduction $f$ of a language $A$ to a language $B$ is a Shorten length reduction, if there exists a number $ n\in N $ s.t for every $ w\in A $, s.t ...
0
votes
1answer
23 views

When reducing from HALT, can you create a Turing machine that asks whether a simulation stops?

Lets say I am doing a reduction from $\mathrm{HALT}_{\mathrm{TM}}$ to another language $S$, in order to prove that $S$ is not decidable. For this I need to build a new Turing machine, $M'$. Can I ...
-3
votes
1answer
62 views

proving that pp closed under cook reductions

I tried to prove or disprove that pp is closed under cook reductions. anyone has a idea or link to a answer?
-1
votes
0answers
36 views

Poly time reduction from 3SAT to 3ALMOST-SAT

I've a final test next week and i'm trying to solve problems from past exams. I get stucked in a question and i'm not sure that my answer is correct, There is a language 3ALMOST-SAT = 3cnf clauses ...
-1
votes
1answer
26 views

Poly-time reduction from HAMPATH to HAMPATH-E

I need to prove that HAMPATH-e = { < G,s,t,e > | G is directed graph, s, t are vertices and e a edge } there is hamiltonian path between s to t that cross the edge e is an NP complete. i've ...
-3
votes
0answers
45 views

Polynomial reduction ,RE and R

Are there any languages L1,L2 such that: L1 is decidable (in R) L2 is Recursively enumerable (in RE) and there is a polynomial reduction between L2 and L1? Thanks.
-4
votes
0answers
18 views

Reductions between CNF-SAT and DNF-SAT

Can someone help me to prove or disprove the following three claims about reductions between CNF-SAT And DNF-SAT? There is polynomial reduction from CNF-SAT to DNF-SAT. There is polynomial reduction ...
0
votes
0answers
27 views

Are there any RE-complete languages w.r.t. polynomial reduction?

I need to decide if there exists $L\in RE$ so that for every $L'\in RE$ we have $L' \leqslant_p L $, meaning a polynomial-time reduction. I've tried to use $L=A_{TM}$ (the accepting problem), but got ...
0
votes
0answers
12 views

Deriving properties of a language based on surrounding reductions

Assume there are three languages: $L_1$, which is the language of the Post correspondence problem (PCP), $L_2$, and $L_3$, which is the complement of the diagonal language. What can be said about $...
-1
votes
1answer
35 views

Languages reducible to and from context-free

Let $L'$ be a context-free language. If $L \leq_M L' \leq_M L''$, where $\leq_M$ denotes mapping reducibility (aka many-one reducibility), what can we know about $L$ and $L''$? I think they're both ...
2
votes
0answers
37 views

Does the Longest Common Subsequence problem reduce to its binary version?

I am working on a problem regarding the Longest Common Subsequence (LCS) of two strings, and I was wondering if there is any reduction from the general case of LCS to its binary version, i.e. by ...
0
votes
0answers
25 views

Deriving properties of a language based on reductions [duplicate]

Assume there are three languages: $L_1$, which is the language of the Post correspondence problem (PCP), $L_2$, and $L_3$, which is the complement of the diagonal language. What can be said about $...
1
vote
0answers
42 views

Why do we need cook reductions?

I have a question about cook reductions and karp reductions. Which is the stronger form? As a cook reduction reduces a search problem to a decision problem which can then be reduced using karp ...
-1
votes
0answers
49 views

Prove that if X is in NP and Y reduces to X, then Y is also in NP

Prove that if X ∈ NP and Y ≤p X, then Y ∈ NP I'm having so trouble with how to go about this proof. I think the steps are to say that X is in NP, and Y reduces to X, therefore if we can solve X, we ...
3
votes
1answer
17 views

Does there always exist equivalent (M)(I)LPs with and without objective functions?

For computing pure Nash equilibria (game theory), there exists a MILP method in literature (clicky). In the proposed MILP, there is no objective function. A solution is a pure Nash equilibrium if it ...
3
votes
1answer
41 views

Can we reduce an NP complete item to an NP item which is $\bf{non}$ P?

I'm curious if we can reduce an $NP$-complete problem to an $NP$ problem which is not a part of the $P$ set. Meaning, can we take an algorithm for this kind of $NP$ problem and use it to solve a ...
-4
votes
0answers
20 views

decidable languages (Computational Models) [duplicate]

I need to prove whether L is decidable or not: L={ | M is a TM and the union of L(M) and H_TM is in RE} ( H_TM={ | M is a TM that halts on w} ) (<M> is the encoding of a TM) THANKS!
4
votes
2answers
51 views

How do you prove that polynomial reductions are not symmetric?

How would I go about showing that L $\leq_p$ L' does not necessarily imply L' $\leq_p$ L? I was thinking I should show an example of two problems, where one can reduce to the other but not the other ...
0
votes
2answers
137 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 ...
1
vote
0answers
44 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
60 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
30 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 ...
-1
votes
1answer
44 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
53 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
19 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
37 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 ...
2
votes
1answer
67 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
51 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
82 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
51 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) = L(...
1
vote
1answer
95 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
48 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} \text{WVC}...
0
votes
1answer
32 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
61 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
147 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
74 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
88 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
67 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 ...