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

213 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
• 162k
165 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 ...
145 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,083
89 views

### Is it possible to reduce functional equations to SAT?

The problem of finding a solution for functional equations can be defined as: Let $A_0, A_1, A_2, \dots, A_n, B_0, B_1, B_2, \dots, B_n, X$ be terms of the $\lambda$-calculus, where all terms are ...
• 4,137
331 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 ...
128 views

• 524
44 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 ...
• 524
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 ...
• 524
91 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 ...
610 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
65 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,101
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, ...
• 807
262 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,275
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 ...
75 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 ...
471 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$ ...
• 395
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$ ...
### Mapping reduction from $A_{TM}$ exercise
Let $L = \{\langle M \rangle \mid \text{M is a TM which accepts only the string "010"}\}$. Prove that $L$ is undecidable. This is my solution, reducing $A_{TM}$ to $L$: $R(\langle M,w \rangle)$ ...