Questions tagged [reductions]

In computability and complexity, finding mappings between problems that allow solving one problem using a solution of another one. For reduction in programming language theory (e.g. beta-reduction), see [lambda-calculus] or [term-rewriting].

Filter by
Sorted by
Tagged with
0 votes
0 answers
20 views

TSP given a length oracle

Consider given a code $C$ that takes as input an edge-weighted graph $((V,E), w)$ and returns the weight of the shortest path that traverses all nodes. How is the minimal number of invocations of $C$ ...
user avatar
  • 1
1 vote
1 answer
55 views

Reducing euclidean TSP of smaller size to euclidean TSP of bigger size

Assume I have a euclidean TSP solver that is optimal, but it can only solve inputs with exactly $N$ vertices. Let's call it the N-solver. Now, I have an input with $K$ vertices in the 2D plane, where $...
user avatar
1 vote
1 answer
38 views

If every NP-hard language is PSPACE-hard then NP=PSPACE

To prove PSAPCE = NP we will show following inclusions : NP $\subseteq$ PSPACE : If every NP-hard language is PSPACE-hard then SAT is also PSPACE-hard. Since every language in PSPACE can be reduced ...
user avatar
1 vote
1 answer
69 views

Generating the n-th number with k bits set, is it possible?

Generating numbers with $k$ bits set for a poker simulation Context I'm trying to generate all possible Texas Hold'em games for $p$ players, which means there will be at most $2 \cdot p + 5$ cards at ...
user avatar
1 vote
1 answer
54 views

Determining whether formula is only satisfied by the all-true assignment

I'm trying to prove that $\mathrm{HALF}\text-\mathrm{FALSE}$ is NP-hard, where $\mathrm{HALF}\text-\mathrm{FALSE}$ is the following problem: given a boolean formula $\phi(x_1,\dots,x_n)$, is there a ...
user avatar
  • 11
0 votes
0 answers
100 views

Prove that neither given language nor its complement is recursively enumerable

Let $L = \{\langle M, n\rangle \mid\,\, n \geq 5000$ and $M$ is Turing machine that halts for every input and leaves at least $n$ non-blank symbols on the tape when stopping $\}$. I believe neither ...
user avatar
1 vote
1 answer
48 views

Worrying about details: high-level arguments about polynomial-time computability

I am learning complexity theory with a background in mathematics, and I want to better understand why certain reductions are polynomial-time computable. Let me give two examples of my worries. Example ...
user avatar
0 votes
0 answers
8 views

connection between self reducibilty and the hardness of the dicison problem

If given that a search problem R is self-reducible, thus we can solve it in polytime steps by (the optional ability of) asking its corresponding decision problem Sr, can I say something regarding the ...
user avatar
1 vote
2 answers
57 views

Why is $A_{TM}$ not mapping reducible to $E_{TM}$?

$A_{TM}= \{ \langle M,w\rangle \mid M$ is a TM that accepts $w\}$ $E_{TM}= \{ \langle M\rangle \mid L(M) = \emptyset \}$ The standard proof for the undecidability of $E_{TM}$ is given in this ...
user avatar
0 votes
1 answer
26 views

reducing the word problem for dtm to sat / cnf-sat / 2-sat

word problem: given a language L through a deterministic turing machine, is the word w in the language L? the problem should be decidable, since if there is a deterministic turing machine i can simply ...
user avatar
3 votes
1 answer
52 views

Why can't $QBF$ be reduced to $SAT$

Let $QBF_k$ be the problem of determining the satisfiability of a formula of the form $Φ = Q_1x_1Q_2x_2 . . . Q_kx_k φ(x_1, . . . , x_n)$. where each $Q_i$ is one of the quantifiers $∀$ or $∃$. So, $Φ$...
user avatar
2 votes
2 answers
61 views

Is the problem of "DFA-TM-INCLUSION" recursively enumerable?

Consider the following problem: Input: A Turing Machine M and a DFA D. Question: Is $L(D) \subseteq L(M)$? Of course, this problem is not decidable. Because it is known that judging whether a word ...
user avatar
0 votes
1 answer
39 views

Reducing to an NP-complete problem

If $R$ is an arbitrary decision problem that is reducible to $S$, which is an NP-complete problem, what can be said about $R$? I think we should be able to say that $R$ is in NP since an instance of $...
user avatar
0 votes
0 answers
8 views

Is it possible to define logspace reductions with FO[TC] queries?

Assume that we have a NP problem A, and a NP-complete problem B under logspace reductions. Furthermore, lets assume that we encode the problem A into a relational database $D_A$, and B into another ...
user avatar
1 vote
1 answer
47 views

$\mathrm{MON} = \{\langle M\rangle : \text{$M$ is monotone}\}$ is undecidable

That's a question from a home assignment by T. Zur: Say that a Turing machine $M$ is monotone if it halts on every input, and if the length of $w$ is greater than the length of $w'$ then $M$ performs ...
user avatar
  • 117
0 votes
1 answer
58 views

Prove that DIFFERENTDFA, PDA {<M1, M2> | Where M1 is a DFA and M2 is a PDA where L(M1)≠L(M2)} is undecidable

I am absolutely stumped on this one. I am unsure of how to start with this one. I have thought to reducing the problem to Atm. Another thought I have had is to convert M1 to a PDA and use the ...
user avatar
  • 1
1 vote
1 answer
50 views

Prove $REJECT\leq_mACCEPT$ and vice versa

a friend of mine sent me a question which he can't solve and I didn't succeed to solve it as well. Question: We define two languages: $$ACCEPT=\{\langle M,w\rangle\ \ |\ M\ is \ a\ turing\ machine.\ M\...
user avatar
1 vote
0 answers
77 views

With fixed k>=4, can 3-coloring in a graph of vertex degree at most k be solved in polynomial time?

I couldn't think of a poly-time solution. Moreover, I think that there is a pretty simple Karp-reduction from 3-coloring problem, which is NP-complete. let's say that graph G is in 3-colloring. I'll ...
user avatar
0 votes
1 answer
64 views

If you can reduce A to B, does that mean B reduces to A?

If you can reduce A to B, does that mean B reduces to A? Sorry for the stupid question. I think the answer should be yes, because if you can convert all yes-instances of A to yes-instances of B, then ...
user avatar
1 vote
1 answer
69 views

On the language of Turing machines that accepts 1 but does not accept 0

I need to find the find the minimal class $\mathcal{L}$ belongs to where $$\mathcal{L} = \{\langle M \rangle: M \text{ is a TM that accepts 1 but does not accept 0}\}.$$ I think I can prove that $\...
user avatar
  • 55
1 vote
2 answers
471 views

Prove that a quadratically-constrained linear program (QCLP) is NP-Complete

Show that if we strengthen linear programming by also allowing constraints of the form $$ \sum_{i,j = 1}^n a_{ij} x_i x_j = b, $$ for integers $b$ and $a_{ij}$, then the problem becomes NP-complete. ...
user avatar
  • 113
1 vote
2 answers
71 views

Reduce instances of a-Turing-machine-does-not-accept-a-string to Turing machines that accept the empty string

I am struggling with a mapping reduction that I think cannot be correct, but I'm not able to say exactly what's the problem. Let $L_{u}= \{\langle M,w\rangle \mid M\text{ accept }w\}$, $\overline{L_{u}...
user avatar
  • 55
1 vote
1 answer
63 views

Prove $H2 = \{\langle M\rangle : M$ accepts all inputs in $\{0, 1\}^∗$ whose length is at most $2\}$ is undecidable but recognizable

Yet another question from an exe. in the Computability class taught by Z. Luria - I'm not really sure how to prove the undecidability, moreover, didn't a finite language always decidable? I mean we ...
user avatar
  • 117
2 votes
1 answer
21 views

Using algorithm for weighted graphs when the weights are vectors

Consider the following example problem. Given a graph with edge weights, find a matching that maximizes the number of matched vertices, and subject to this, maximizes the total weight. This problem ...
user avatar
0 votes
1 answer
51 views

Prove that EXIST = {$<M>$:There exists a string $w ∈ Σ*$ such that $M$ halts on $w$} is undecidable

This is a question by my professor Z. Luria in my Computability course. My first approach was to try and prove it by contradiction, assuming that EXIST is decidable and using the algorithm that ...
user avatar
  • 117
1 vote
0 answers
15 views

example of an NL-completeness reduction?

I'm looking for simple examples of nondeterministic log-space completeness reductions. In particular I seem unable to construct any nontrivial widget using 2-SAT clauses, which is known to be NL-...
user avatar
0 votes
1 answer
34 views

Turing recognizability and Reduction Mapping on pairs of related Turing machines

I am interested in computation and I am lost on undecidability and reductions. I have the following two problems I am stuck on. Let us call 2 Turing machines related if there is an input $w$ on which ...
user avatar
0 votes
0 answers
30 views

If $S$ is non-trivial, there is $S' \neq S$ which is Karp-equivalent to $S$

Prove or refute: For all decision problem $S⊆\{0,1\}^*$ such that $S≠∅, \{0,1\}^*$ there is a decision problem $S'⊆\{0,1\}^*$ that is different from $S$ such that there is a Karp reduction from $S$ to ...
user avatar
  • 1
1 vote
0 answers
23 views

Assumptions needed by Exact Cover by 3-Sets (X3C)

The problem is defined as https://npcomplete.owu.edu/2014/06/10/exact-cover-by-3-sets/: Given a set $X$, with $|X| = 3q$ (so, the size of $X$ is a multiple of $3$), and a collection $C=\{(x_{i1},x_{...
user avatar
  • 65
3 votes
1 answer
86 views

Determine efficiently whether A can get infinitely larger than B by following a walk in the given graph

Person $A$ is chasing person $B$. Both people can only travel between $n$ vertices of a graph by running through one of $m$ one-way pipes labelled $1,2,\cdots, m$. For each pipe we know the starting ...
user avatar
3 votes
0 answers
58 views

Low-rank matrix completion is NP-hard

In looking into the problem of low-rank matrix completion / relaxations of the general problem to derive exact solutions, many papers cite that the original formulation is NP-hard but I cannot find a ...
user avatar
-2 votes
1 answer
34 views

Decision problem

Prove the following theorem Let A and B be two languages on an alphabet Σ. If A ≤p B and B ∈ P, then A ∈ P. Could anyone be able to prove it?
user avatar
  • 1
0 votes
0 answers
21 views

If a problem is Cook-reducible to a problem in NEXP, is it in NEXP too?

I get why that would be true for EXP but cannot extend the argument to NEXP.
user avatar
1 vote
1 answer
46 views

Are all $\mathbf{P}$ languages $\mathbf{P}$-complete with respect to polynomial-time reduction?

Question: Is language $L \in \mathbf{P}$ also $\mathbf{P}$-complete with respect to polynomial-time reduction? My thoughts: Given a language $L \in \mathbf{P}$, we want to show that for any other ...
user avatar
1 vote
1 answer
47 views

Proof of NP-hardness of the k-means clustering problem for $k\geqslant 3$

coming from the computing science side rather than from the data analysis one, I studied the k-means clustering problem for a short time and noticed that the NP-hardness of the problem for $k=2$ seems ...
user avatar
2 votes
1 answer
42 views

Is there a non PSPACE language s.t exponential padding of it is PSPACE?

I've had an exam in computational models a few days ago, and would like to check whether I made a mistake. The question goes like that: Is there a language $ L \notin PSPACE $ over the alphabet {0,1} ...
user avatar
  • 21
1 vote
1 answer
73 views

Why NP-Complete reduction is not reversible?

I have read the question asked here Is polynomial reduction reversible and the logic actually makes sense to me. In other words, if A is polynomially reducible to B, it means that A <= B in terms ...
user avatar
  • 65
1 vote
1 answer
470 views

Show that a subproblem of Sparse Subgraph is $\mathcal {NP}$-Complete

I want to show that a subproblem of the known, $\mathcal {NP}$-Complete, Sparse Subgraph problem is also $\mathcal {NP}$-Complete. Sparse Subgraph problem: Input: Undirected graph $G(V,E)$, two ...
user avatar
  • 133
0 votes
0 answers
37 views

Polynomial reduction to SAT with a condition

Let L be in NP. Is there always a reduction from L to SAT where atleast m-1 clauses (m being the number of clauses in the CNF formula) can be satisfied? When w is in L it is trivial because the ...
user avatar
2 votes
0 answers
73 views

Limited number of calling for a decision blackbox to compute all the solutions

I am trying to reduce between a solution problem and a decision version of the same problem. The problem is the orthogonality problem. Given $2$ sets $L$ and $R$, whose size each is $n$ vectors over $\...
user avatar
0 votes
0 answers
36 views

If $L_1 \leq_m L_2$, and $L_2$ is decidable, is $L_1$ then decidable?

There is a lemma in our textbook that asks us to prove the following: If $L_1 \leq_m L_2$, and $L_2$ is decidable, then $L_1$ is decidable I tried proving this by saying that if $L_1 \leq_m L_2$, ...
user avatar
1 vote
1 answer
54 views

reduction from 3SUM to 3ARR-ARITH

The 3SUM problem is defined as follows. Given an array A[1...n] of numbers, determine whether there exist $i,j,k\in \{1,\cdots, n\}$ so that $A[i] + A[j]+A[k] = 0$. The 3ARR-ARITH problem is defined ...
user avatar
2 votes
1 answer
59 views

Reducing a CNF formula to a DNF formula in less than exponential time

The easy way is by looking at the $\{0,1\}$-table and construct the corresponding DNF formula from that, but this will take $2^n$ time. I want to do it much more efficiently. My idea is based upon the ...
user avatar
  • 314
4 votes
1 answer
76 views

Attempt to reduce to problem of inner product

The problem of Orthogonality: gives $n$ vectors of dimension $k$ and another set of same, can a pair be found with inner product = $0$? The problem of max product: likewise two sets each $n$ vectors (...
user avatar
0 votes
0 answers
24 views

Reduction from SAT to EXACTSAT

PROBLEM: EXACTSAT INPUT: A boolean formula $\phi$ in CNF with $n$ variables, and a natural number $k \le n$. OUTPUT: "Yes" if and only if there is truth assignment $\theta$ which sets ...
user avatar
0 votes
0 answers
40 views

In-place Acceptance Problem

In-place Acceptance Problem (InAP) Instance: A deterministic Turing Machine M and a w input for it. Question: Does M accept the input w without going through cell (|w|+1)? Show that InAP is PSPACE-...
user avatar
1 vote
1 answer
23 views

Can I reduce from the recognition version of one probem to another without knowing the exact parameter?

I was reading the paper "Kou, L. T., Stockmeyer, L. J., & Wong, C. K. (1978). Covering edges by cliques with regard to keyword conflicts and intersection graphs. Communications of the ACM, 21(...
user avatar
0 votes
1 answer
35 views

Help in proving L-Completeness

I'm trying to prove that the following language is L-complete A is a language where each word is comprised of 0s and 1s & the number of 0's is double that of the number of 1's So far I've managed ...
user avatar
  • 135
2 votes
1 answer
412 views

How to reduce SUBSET-SUM with integers to SUBSET-SUM with non-negative integers?

The subset sum problem is as follows: Given a sequence of integers $\mathcal S=(a_1, ..., a_n)$ with cardinality $n$ and an integer $T$, determine whether there is a subsequence of $\mathcal S$ whose ...
user avatar
2 votes
0 answers
33 views

Non-trivial reduction form SAT to $3$-SAT

Looking for any idea for reduction from $SAT \leq 3-SAT$ where $SAT$ is known to have $d$ variables at most in each clause. I am looking for a reduction in which the resulting formula will not depend ...
user avatar

1
2 3 4 5
24