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].

136 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
28
votes
0answers
793 views

Graph problem known to be $NP$-complete only under Cook reduction

The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a ...
18
votes
1answer
1k views

Could min cut be easier than network flow?

Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
6
votes
0answers
141 views

Any Natural Problems shown Easy by Reduction to Horn SAT?

To show that a problem is polynomial-time solvable, an often-successful technique is to reduce it to 2SAT (that is the problem of deciding satisfiability of CNF formulas with every clause containing ...
6
votes
1answer
127 views

Weakest reduction for P-completeness

It is common to define $P$-completeness with respect to logspace many-one reductions. I am looking for a complexity class $C$ such that if $C=P$ then all problems in $P$ are $P$-complete under many-...
6
votes
0answers
128 views

NP-hardness of a special traveling salesman problem

Consider we have $n$ vertices, $v_1,\ldots,v_n$. We have two positive values $(a_i,b_i)$ associated with each $v_i$. The edge weight $w(v_iv_j)=a_ia_j+b_ib_j$. Is it NP-hard to solve the traveling ...
5
votes
0answers
256 views

Reduce factoring to solving quadratic equations

The problem of solving quadratic equations is as follows: Suppose you are given a set of quadratic equations and are asked to find $0$-$1$ values for the variables such that all equations are ...
5
votes
0answers
114 views

Reduction from clique to bag automata

I am trying to figure out a reduction to prove $W[1]$-hardness for this, but I am having significant trouble. Here is the problem: Bag Automaton: A non deterministic finite state automaton $M=(Q,I,s,...
5
votes
0answers
229 views

Find a permutation that maximize the minimum of $\frac{a_n}{a_{n-1}} + \frac{a_n}{a_{n+1}}$

Consider a sequence of $n$ positive real numbers $a_0,\ldots,a_{n-1}$. Let $S_n$ be the set of permutations on $\{0,\ldots,n-1\}$. We are interested to find $$ \max_{\pi\in S_n}\left( \min_{i=0}^{n-...
4
votes
0answers
81 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 ...
4
votes
0answers
85 views

Proof that $P$ is robust against switching between polynomially equivalent encodings

Lemma 34.1 Let $Q$ be an abstract decision problem on an instance set $I$, and let $e_1$ and $e_2$ be polynomially related encodings on $I$. Then, $e_1(Q)\in \mathrm{P}$ if and only ...
4
votes
0answers
101 views

Quality of Reduction of finite automata using different congruences

I am looking for an example, which corresponds to what I've learned in my Applied Automata Theory Class: Given a NFA $\mathcal{A}$, a $\approx _\mathcal{A}$ quotient automaton can be bigger then a $...
4
votes
1answer
126 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 ...
3
votes
1answer
147 views

Undecidability of two Turing machines acting the same way on an input

So I need to find a reduction to the (undecidable) problem of deciding if two Turing machines $M_1$ and $M_2$ behave the same way on an input $x$. "Behaving the same way" is defined like this: $M_1$ ...
3
votes
0answers
76 views

Proving NP-completeness of an extension in List Coloring Problem

In the List Coloring Problem (LCP), one is given an undirected graph $G(V,E)$, each vertex $v \in V$ is given a list of permissible colors $L(v) \subseteq \{1,2,\dots,k\}$, we want to find a coloring $...
3
votes
2answers
273 views

Solving the min edge cover using the maximum matching algorithm

To solve an instance of an edge cover, we can use the maximum matching algorithm. Edge Cover: an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least ...
3
votes
0answers
208 views

Minimum clique cover

How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time? Having an undirected graph, I am trying to partition all its ...
3
votes
0answers
89 views

A special case of the SUBSET SUM problem

Consider the following special case of SUBSET SUM Inputs: Positive integers $a$ and $b$ with $a \ne b$, and positive integers $k$ and $t$, with $k$ specified in unary. Encoding: These inputs (...
3
votes
1answer
115 views

Efficient algorithm to determine if a lambda calculus term is equivalent to one without a given free variable

Consider the following problem: given a lambda calculus term $t$ and free variable $v$ determine whether $\phi(t,v)$, where $\phi(t,v) := \exists t'. t' \equiv t \land v \notin FV(t')$. This problem ...
3
votes
0answers
72 views

Direct reduction $L_{REG}\le_m L_{CFG}$

Both $L_{REG}=\{ \langle M \rangle : L(M)\text{ is regular}\}$ and $L_{CFG}=\{ \langle M \rangle : L(M)\text{ is context-free}\}$ are $\le_m$-complete for $\Sigma_3^0$ in the arithmetic hierarchy. ...
3
votes
0answers
77 views

Is there a reduction concept in artitificial intelligence?

Is there a concept for comparing algorithms in artificial intelligence theory similar to reduction in complexity theory (Wikipedia)? I'm asking this because I was wondering how AI algorithms are to ...
3
votes
0answers
339 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 ...
3
votes
0answers
332 views

smallest satisfiability-equivalent formulas (generalized Tseitin transform)?

What is known about the following optimization problem for formulas in propositional logic: input: formula $F$ output: formula $G$ in CNF with $\mathrm{Var}(G) \supseteq \mathrm{Var}(F)$ such that ...
3
votes
0answers
74 views

What is an upper bound on formula size when converting 3-SAT to UNIQUE 3-SAT?

What is an upper bound on formula size when converting 3-SAT to UNIQUE 3-SAT? We can use the Valiant Vazirani Therom, also found here (in more detail). Essentially, it is a randomized algorithm that ...
3
votes
0answers
93 views

Hardness of a special case of maximum matching

Input: A set of $n$ Users $U=\{u_1, ..., u_n\}$ and a set of $m$ products $I=\{i_1, ..., i_m\}$. Associated with each pair $u \in U$ and $i \in I$ is the probability $p_{u,i}$ of $u$ purchasing the ...
3
votes
0answers
285 views

Non-self-reducible NP problem

I am interesting in proving that there is no search problem that is polynomial bounded and self-reducible, as long as ${\sf P} \neq {\sf NP} \cap {\sf coNP}$. The problem is I don't know how to ...
3
votes
0answers
432 views

Hardness of counting solutions to NP-Complete problems, assuming a type of reduction

The $\text{NP-Complete}$ class of problems is defined w.r.t Karp Reductions, which are polytime many-one reductions. However, they need not necessarily preserve the number of solutions. A more ...
2
votes
0answers
22 views

Concurrent Element-wise Reduction Algorithm (multi-threaded) (C++)

I'd like to implement a high-performance implementation of a multi-threaded reduction, element-wise, on x86 CPUs. Without loss of generality, assume the reduction operation is a sum of integers (so, ...
2
votes
0answers
30 views

NP-completeness of Induced disjoint paths between a set of sources and a set of sinks

In a given undirected graph $G(V,E)$, a set of $k$ paths is said to be induced if: They are vertex-disjoint. Each one is itself an induced path. No edge connects two vertices of two different paths. ...
2
votes
1answer
163 views

Why is Graph Isomorphism downward self reducible?

To say that graph isomorphism is downward self reducible means the following: There is an algorithm which decided graph isomorhpism for two given graphs of n vertices in polynomial time by accessing ...
2
votes
0answers
38 views

Is the language $L$ of coded CFG's Turing decidable?

Consider the following language $L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$} Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
2
votes
0answers
53 views

Reducing a problem to 2-SAT

Given a matrix $A$ with entries $a_{ij} \in \{0,1\}$, the matrix $B$ is formed by $b_{ij}=a_{ij} + a_{i+1,j} + a_{i,j+1} + a_{i+1,j+1}$. $B$ has one row and one column less than $A$. The problem is ...
2
votes
2answers
176 views

Circuit satisfiability problem : SAT-C to SAT-2C

I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C. Prove that ...
2
votes
0answers
107 views

Why gap preserving reduction is weaker than L-reduction?

In Vizirani's textbook says in page 332, Gap preserving reductions are weaker than their L-reductions [...] one of the motivations for the PCP theorem was that establishing an inapproximability ...
2
votes
0answers
207 views

Practical usage of the λ-calculus self-interpreter and the self-reducer?

I came across the paper: "Efficient Self-Interpretation in Lambda Calculus" by Torben Mogensen, 1994: http://repository.readscheme.org/ftp/papers/topps/D-128.pdf It talks about the intepreter $E$ ...
2
votes
0answers
112 views

Growth of non-terminating beta reductions in lambda calculus

There are some terms in lambda calculus that don't really have a normal term. My question is for a term like the following: $$T \overset{def}{=} \lambda f. (\lambda x. \; f \; (f \; (f \; x)))$$ $T$ ...
2
votes
0answers
4k views

Reduction of 3-SAT to Vertex Cover?

Can someone explain to me in the simplest possible way, how to reduce $3SAT$ to $Vertex\:Cover$? I am following the explanation here (scroll to the bottom of page 4). I understand the basic setup of ...
2
votes
0answers
139 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 $a_1, a_2, \dots, a_n$. Question: Can the list be partitioned into $2$ parts, $A_1$ and $A_2$, such ...
2
votes
0answers
127 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 ...
2
votes
0answers
273 views

Ideas on reducing Traveling Salesman to Metric Traveling Salesman?

I want to show a polynomial reduction from TSP to Metric TSP. I know the rule is: $(G, k) \in TSP \iff (G', k') \in MTSP$ where $G$ is some graph, and $k$ is some bound. It seems like whatever I map $...
2
votes
0answers
49 views

What are the fundamental principles/algorithms on the process of equation solving?

I have seen a lot of solvers that are capable of, for example, getting an equation such as x ^ 2 + x = 12 and finding x = [3, -4]. I know some of them are implemented by hardcoding special cases. For ...
2
votes
0answers
120 views

Constructing a promise problem equivalent to XSAT from subset sum

Consider $\Pi$ to be the problem to decide if there is a subset of numbers that sum to $0$ in the given list of integers. How does one construct a promise problem equivalent to $xSAT$ from this? $...
2
votes
0answers
107 views

Karp reduction between FACTORING and a variant of it

Consider the following variant of the FACTORING problem (given N,M decide whether N has a prime factor less than M): MULTIPLE-FACTORING: Given three integers $1 \leq K \leq M \leq N$ decide if there ...
1
vote
0answers
32 views

Complexity problem reduction?

Let say A and B are two decesion problems where A $\le$ B polinomial reduction is true. Is this : A̅ $\le$ B̅ also true? If so, can you show an exemple, if not why?
1
vote
0answers
45 views

PSPACE-hardness of the unbounded puzzle

Given a board of size $n \times 1$ where $n=\infty$ (basically a tape, one way infinite), and a set of colors $C$, some starting color $c_{start} \in C$, a set of templates $T$ in a form $(c_k, i, c_i,...
1
vote
0answers
20 views

Show that SQUARED-SUM-PARTITION is NP-complete

Consider the following problem SQUARED-SUM-PARTITION. You are given positive integers $x_1, \dots, x_n$, and numbers $k$ and $B$. You want to know whether it is possible to partition the numbers $\{ ...
1
vote
0answers
11 views

Decide if Turing machine's language contains either a or b string

during school exercises we worked on decidability problems and there was one I don't really understand. We were provided with solution and explanation regarding this exercise but still I need more ...
1
vote
0answers
35 views

How do I go about creating a mapping reduction?

So I understand what a mapping reduction is and how to create them for simpler problems such as a reduction from the set of even numbers to set of odd numbers however, seemingly more complicated ...
1
vote
0answers
48 views

Reduce duplicate subset sum problem to distinct subset sum problem?

In duplicate subset sum problem (DuSSP), we are given a multiset $\{a_1,a_2,\ldots,a_n\}$ where some of the $a_i$ are duplicates. We can assume that $a_1\leq a_2\leq \cdots\leq a_m.$ We are also given ...
1
vote
0answers
16 views

What are the requirements for a superset of P to be closed under karp reductions?

So today in our exercise session on complexity theory we discussed that P, NP, and BPP are closed under karp reduction. We also figured that the proofs could likely be expanded to straight ...
1
vote
1answer
84 views

How to encode reachability in a graph with walls as a SAT problem

Suppose we have a graph that represents a grid of cells. We are given a cell to start in and a cell that's the destination. There are cells that we cannot enter and they are known as walls. Finally we ...