# Questions tagged [reductions]

A reduction is the transformation of one problem into another problem. A example of using a reduction would be to be to show if a problem P is undecidable. This would be achieved by transforming or performing a reduction of a decision problem $P$ into an undecidable problem. If this can be achieved then we have shown that this problem P is undecidable.

215 questions
Filter by
Sorted by
Tagged with
25 views

### Reduction from any succinct language to tiling

Given a set of colors $T = \{1, \ldots, k\}$, a set of horizontal or vertical rules $H, V \subseteq T \times T$ of ordered pairs, and a chosen color $b = 1$, the tiling language is defined as follows: ...
124 views

### How to prove that a problem is not smoothed-polynomial?

Many research works use Smoothed analysis to prove that some NP-hard problems can actually be solved efficiently in typical cases. A different notion with a similar goal is Generic-case complexity. ...
69 views

### Is a problem, that is $L$-complete under non-uniform $AC^0$ reductions, necessarily outside of (non-uniform or uniform) $NC^1$?

I don't have much intuition about non-uniformity so the question may be quite naive.
19 views

### Natural reduction from partially observable Markov decision process planning to reconfiguration

Suppose I want to prove the PSPACE-completeness of reconfiguration by reducing partially observable Markov decision process (POMDP) planning to it. Is there a known natural / succinct reduction from ...
1 vote
65 views

### Is this kind of "multi-reduction" interesting?

Given a decision problem $P$, the usual way to show that it is NP-hard is to find a known NP-hard problem $Q$, and show a polynomial-time algorithm that transforms every instance $I_Q$ of $Q$ to an ...
116 views

### Can you find a counterexample / disprove my P=NP solution?

I've posted the full article here. The source code is available here. Basically, in the Linear Programming (LP) task, we solve a system of inequalities: one inequality per BSAT clause. In each ...
6k views

### Fast Reduction from RSA to SAT

Scott Aaronson's blog post today gave a list of interesting open problems/tasks in complexity. One in particular caught my attention: Build a public library of 3SAT instances, with as few variables ...
178 views

### This is a variant of the unsolved problem of $a^6+b^6+c^6≠d^6+e^6+f^6$, for distinct primes. Does it have any significance for Exact Three Cover?

Suppose, I'm solving Exact 3 Cover, given a list with no duplicates $S$ of $3m$ whole numbers and a collection $C$ of subsets of $S$, each containing exactly three elements. The goal is to decide if ...
1 vote
70 views

### Why is the model-checking problem for MSO $\textsf{PSPACE}$-complete?

I am currently reading "Parameterized Complexity Theory" by J. Flum and M. Grohe. In Chapter 10.3 they state in the first paragraph: Let us remind the reader that the model-checking problem ...
72 views

### Reductions That Acts on Witnesses

We say that a language $X$ is polynomial time reducible to $Y$, intuitively, if given an algorithm for solving $Y$, there's an algorithm for solving $X$. I know this can be formalized using Karp ...
315 views

### Proving #P-hardness for the number of subsets of a set of positive integers with a sum of at most T?

Consider the given problem: you have a set S of positive integers, and you want to find how many subsets have a sum of at most T. I highly suspect that the problem is hard since a polynomial time ...
98 views

### strong NP-completeness of multi-dimensional Equal-Subset-Sum

I want to show that the multi-dimensional Equal-Subset-Sum is NP-complete in the strong sense: Given a set of $d$-dimensional vectors of non-negative integers, does there exist two distinct nonempty ...
39 views

### converting K-SAT clause to a p-in-L-SAT equation

Given a generic K-SAT instance $S$ with $n$ boolean variables. Is it possible to convert a clause of this instance into an equivalent p-in-L SAT system of equations such that the number of new clauses ...
5k views

76 views

110 views

### Need more explaination on this 'generality'

I am trying to understand how this proof works I don't understand, why this f' is nondecreasing? What kind of generality makes us come up with such kind of assumption? Please, I am weak.
138 views

### Showing that a modification of an NP-Complete problem is also NP-Complete

In this question I give a modified version of the knapsack problem, which I call the "extended knapsack problem". I want to show that this "extended" problem is NP-Complete, but I ...
902 views

### How to prove fooling set problem to be NP-hard

I read in a paper showing that it can be implemented by reducing induced matching problem on bipartite graphs to fooling set. But the proof was omitted in that paper and I cannot find answer by myself....
202 views

### Parameterized complexity of Hitting Set with slightly bigger parameter

The Hitting Set problem, when parameterized by the size $k$ of the hitting set, is W[2]-hard. Is it also W[2]-hard when parameterized by $k$ plus the number of subsets in the instance? I explain in a ...
97 views

### Reducing counting minimal vertex covers to counting minimum cardinality vertex covers

Consider two problems. Problem 1: Given a graph $G = (V, E)$, find the number of minimum cardinality vertex covers of $G$. Problem 2: Given a graph $G = (V, E)$, find the number of minimal vertex ...
394 views

### Invisible electric fence even if P = NP?

Scott Aaronson has suggested that one argument in favor of $\mathsf{P} \ne \mathsf{NP}$ is that there seems to be an invisible electric fence separating $\mathsf{NP}$-complete problems from problems ...
253 views

### Does such a graph exist? [closed]

[EDITED FOR CLARITY] Does there exist an edge-colored graph $G$ with the following properties? $G$ has a vertex $r$ with exactly three, distinctly colored, incident edges: $(r, u)$, $(r, v)$, $(r, w)$...
105 views

### Worst to average case reductions for quantum complexity classes

I am studying worst to average case reductions for different complexity classes. Consider quantum complexity classes like QMA, QSZK, or QIP. Is it known or believed that these classes are amenable to ...
1 vote
247 views

### Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?

In "Classic Nintendo Games are (Computationally) Hard", a generalized framework based on reducibility of 3-SAT for proving NP-hardness of classic Nintendo games is presented, and several ...
I'm trying to figure out the complexity of the reachability problem having as input a directed rooted forest, i.e., given a set of directed rooted trees and two vertices $s$ and $t$, tell if $s$ and $... 1 vote 0 answers 144 views ### A reduction from the maximum$k$-closure problem to the clique problem Fix a partially ordered set$(P, \le)$with$N$elements and real weights$w(p)$for each$p \in P$. A subset$S \subset P$is called closed if for any$x, y$with$y \in S$and$x \le y$we also ... 3 votes 1 answer 172 views ### complexity class of a function - linear combinations and reductions (Fermionant, immanant,$GL_n$representations) The fermionant is a matrix function from physics, which is indexed by a positive integer$k: \begin{align} \operatorname{Ferm}_k(A) = \sum_{\lambda} d_{\lambda}^{(k)} \operatorname{Imm}_{\lambda^T}(A)... 2 votes 1 answer 1k views ### 3SAT to 1-in-3SAT reduction with additonal constraints The simplest Reduction for 3-SAT to 1-in-3-SAT reduction is as follows: For each 3SAT clause:x+y+z=1$Introduce 4 new variables$\{a, b, c, d\}$and replace original clause with below 3 clauses:$R(...
As per this paper by Grädel, Kolaitis and Moshe Vardi, they discuss computational complexity of satisfiability problem in $\mathrm{FO^2}$, In order to do this they use Scott's reduction. Which is the ...