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].
215
questions with no upvoted or accepted answers
19
votes
1
answer
2k
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 ...
D.W.♦
- 152k
7
votes
0
answers
150
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 ...
- 363
6
votes
0
answers
142
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 ...
- 3,023
5
votes
0
answers
319
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
...
- 51
5
votes
1
answer
221
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-...
- 4,387
5
votes
0
answers
128
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
0
answers
235
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-...
- 3,023
4
votes
0
answers
221
views
Reduction from 3-partition to ABC-partition
The ABC-partition problem is a variant of 3-partition in which, instead of a single set $S$ with $3 m$ positive integers, there are three sets $A, B, C$ with $m$ positive integers in each. The goal is ...
- 5,844
4
votes
0
answers
2k
views
Is protein folding really NP-hard and how to show that?
This question has two facets that are related.
Is the general problem of protein folding really NP-hard?
The hydrophobic-polar protein folding model (Ken Dill et al., 1985) stated the problem on a ...
- 259
4
votes
0
answers
84
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. ...
- 216
4
votes
0
answers
573
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 ...
- 41
4
votes
0
answers
95
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 ...
- 5,342
4
votes
0
answers
92
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 ...
- 41
4
votes
0
answers
106
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 $...
- 534
4
votes
1
answer
154
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 ...
- 494
3
votes
0
answers
54
views
Is there such a thing as $coW[1]$-hardness?
I have a problem $\mathsf{A}$ and I would like to analyze its (parameterized) computational complexity.
I found a parameterized reduction from the complement of the independent set ($\mathsf{coIS}$) ...
- 31
3
votes
0
answers
39
views
Can fine-grained hardness be proved directly from classical hardness (e.g., $\sf P \neq NP$) in some way?
I have just learnt about some typical result of fine-grained hardness in 15-455 by Prof Ryan: CNF-SETH implies ${\sf DIAMETER} \notin {\sf TIME}(mn^{1-\epsilon})$. (Here DIAMETER stands for the graph ...
- 301
3
votes
0
answers
118
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 ...
- 31
3
votes
0
answers
57
views
Sufficient condition for a complexity class's closure under NP-reductions?
Let us say that there exists a $\mathsf{NP}$-reduction from a problem $A$ to another problem $B$ when there exists a non-deterministic, polynomial-time Turing machine $T$ such that for each $a \in A$, ...
- 31
3
votes
0
answers
58
views
Standardisation Theorem versus Leftmost reduction Theorem
According to Chris Hankin in his book (Lambda Calculus a Guide for Computer Scientists). A reduction sequence $\sigma: M_0 \to^{\Delta_0} M_1 \to^{\Delta_1}M_2 \to^{\Delta_2}\ldots $ is a standard ...
- 31
3
votes
1
answer
458
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 ...
- 155
3
votes
0
answers
170
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, ...
- 153
3
votes
0
answers
111
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
0
answers
787
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 ...
- 31
3
votes
0
answers
164
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 (...
- 131
3
votes
0
answers
174
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 ...
- 729
3
votes
0
answers
86
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 ...
- 273
3
votes
0
answers
441
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 ...
- 141
3
votes
0
answers
88
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 ...
- 882
3
votes
0
answers
97
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 ...
- 31
3
votes
0
answers
359
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,139
3
votes
0
answers
529
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 ...
- 365
2
votes
0
answers
26
views
Are $\mathsf{L,NL}$ closed under reverse operation?
for a language $L$ we define $rev\left(L\right)=\left\{ \sigma_{n}\cdot\ldots\cdot\sigma_{1}\mid w=\sigma_{1}\cdot\ldots\cdot\sigma_{n}\in L\right\} $.
My question is, are $\mathsf{L,NL}$ closed under ...
- 141
2
votes
0
answers
45
views
Proving the language 2-SIMPLE-PATH is in NL
The Question
I define the language$$\mathsf{2-SIMPLE-PATH}=\left\{ \left\langle G,s,t\right\rangle \left|\begin{array}{c}
\mathsf{there\;are\;two\;different}\\
\mathsf{simple\;paths\;from}\;s\;\...
- 145
2
votes
0
answers
30
views
Reductions from 3-SAT that won't work directly from SAT
Our prof talked about why it's good to know that 3-SAT is NP-complete because it's easier to craft reductions from it than from plain SAT.
However, all the examples we've seen (reduction to ...
- 21
2
votes
0
answers
76
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 $\...
- 494
2
votes
0
answers
34
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 ...
- 494
2
votes
0
answers
39
views
How far would complexity hierarchies collapse if $L\in CoNP$ is $L\in NPH$?
Let $L\in CoNP$. Assuming that $L\in NPH$, what would we get?
So, as $L\in NPH$ then every language $A\in NP$ has a reduction $A \leq L$. This would mean that $\overline{L} \leq L$ as well. By ...
- 494
2
votes
0
answers
83
views
Why do I only need to reduce from one problem in NP to prove NP-Hardness?
Suppose I wish to show that my decision problem $Q$ is NP-Hard. Why do I need to reduce from one problem $Q'$ of known hardness ?
Consider for instance the following situation:
Here, I have my set NP ...
- 121
2
votes
1
answer
80
views
Proving that DCONN is NL-Complete
I am having trouble with some homework regarding proving that DCONN is NL-Complete. As part of the exercise, the fact that RCH is NL-Complete can be assumed.
Problem definitions:
RCH: Given a ...
2
votes
0
answers
400
views
Reducing Dominant Set Problem to SAT
I am trying to solve a problem and I am really struggling, I would appreciate any help.
Given a graph $G$ and an integer $k$ , recognize whether $G$ contains dominating set $X$ with no more than $k$ ...
- 53
2
votes
0
answers
60
views
Reducing Kleene's predecessor for Church numerals
I am trying to "reinvent" Kleene's predecessor myself. The following code snippet should be self-explanatory. The idea is to make a 2-tuple and count up from zero, i.e. ...
- 1,071
2
votes
0
answers
55
views
Why can the construction of a polynomial-sized structure be done in logspace?
In paper http://www.iro.umontreal.ca/~mckenzie/Recherche/homc10fun.pdf the authors prove their problem is NL-complete. At some point in their proof however, they construct a polynomial-sized graph, ...
- 675
2
votes
0
answers
644
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 $\{ ...
- 175
2
votes
0
answers
224
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,245
2
votes
0
answers
47
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 ...
- 33
2
votes
0
answers
72
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 ...
- 21
2
votes
1
answer
502
views
Invertability of Karp reductions
Karp reducibility between NP-complete problems $A$ and $B$ is defined as a polynomial-time computable function $f$ such that $a \in A$ if and only if $f(a) \in B$.
I am interested in polynomial-time ...
- 4,387
2
votes
0
answers
433
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$ ...
- 385
2
votes
0
answers
132
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$ ...
