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.
217
questions
-1
votes
0
answers
21
views
Is it possible for two languages in NOT ( R E ∪ c o − R E ) to not have a reduction between them?
In computability theory, the class NOT(RE∪co−RE) refers to languages that are neither recursively enumerable (RE) nor co-recursively enumerable (co-RE). These languages are considered to be highly ...
2
votes
0
answers
30
views
Is PP non-adaptively random self reducible?
It is well known that $\mathsf{\#P}$ is non-adaptively random self-reducible, with the common proof given via the permanent. Feigenbaum and Fortnow showed that this implies $\mathsf{PP}$ is adaptively ...
- 61
0
votes
0
answers
31
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:
...
- 11
5
votes
1
answer
125
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.
...
- 2,294
0
votes
0
answers
79
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.
- 43
0
votes
0
answers
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 ...
- 828
1
vote
0
answers
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 ...
- 2,294
-4
votes
1
answer
127
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 ...
- 101
0
votes
1
answer
179
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 ...
- 159
1
vote
0
answers
73
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 ...
- 181
0
votes
0
answers
77
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 ...
0
votes
2
answers
101
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 ...
- 101
0
votes
0
answers
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 ...
- 831
4
votes
1
answer
237
views
Is Optimal Swap Sorting NP-Hard?
Given an array of integers with duplicates, find the minimum number of swaps to sort the array. According to this question, the problem is NP-Complete but the reference given proves NP-Completeness ...
- 135
7
votes
2
answers
316
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 ...
- 135
2
votes
1
answer
97
views
Set Cover with Multiple covers
I am interested in whether a set cover instance that covers all elements $q$ times may have the property that every sufficiently small subset of this set cover will not cover the elements even once. ...
- 412
0
votes
0
answers
101
views
Complexity of Identifying SAT Problems with a Unique Solution from Satisfiable Instances
I am curious about the computational complexity involved in identifying SAT problems that have only one solution from a set of satisfiable SAT instances.
input and output: input: A satisfiable cnf ...
- 316
0
votes
0
answers
34
views
Nonlinear GAP similar to Min-GAP but with minimum quantities and without capacity
I have $m$ items and $n$ bins where each item $i$ and bin $j$ has a value $v_{i,j}$. Each bin $j$ has a value $V_j$. I want to pack the items into the bins such that
(1) I minimize the ratio of the ...
- 115
6
votes
0
answers
181
views
Variation of (derandomized) Valiant-Vazirani
I am interested in the following "improvement" of the Valiant-Vazirani reduction. As pointed out here, under the right derandomization assumptions one can obtain a deterministic polynomial-...
- 1,029
5
votes
1
answer
159
views
Are there complexity teaching resources that do not treat NP-hardness gadgets as Voodoo magic?
I am teaching a mini-complexity course to high achieving high-school students from my country this fall, and they have all expressed strong interest in learning more about what $P, NP$, reductions, ...
- 1,153
3
votes
0
answers
88
views
Is universal hashing fully black-box reducible to error correcting code?
Fully black-box reduction is defined as in Notions of reducibility between crytpographic primitives, O. Reingold et al.
Error-correcting code is used in the black-box abstract way in the sense that ...
- 161
1
vote
0
answers
78
views
Using a certificate in the proof of NP hardness
Say I wanted to determine that the problem of membership in some language $L \subseteq \{0, 1\}^*$ is NP-hard. Say that I have a reduction $r: \{\text{set of quantifier free formulas} \rightarrow \{0,...
- 21
5
votes
1
answer
77
views
Does there exist constant overhead reduction between common cryptographic primitives?
I have proved that there exist such reduction between error-correcting codes and exposure resilient functions, which is because that the transpose of a generator matrix for a ERC mapping $\mathbb{F}_2^...
- 161
2
votes
0
answers
120
views
Does GHC use graph reduction?
I have read somewhere that GHC does not use graph reduction for compiling/evaluating expressions. Is this right? If yes, what does it use as an alternative?
- 131
0
votes
0
answers
77
views
On the Reductions of Functional complexity Classes
In Chapter 10 of Computational Complexity by Christos Papadimitriou, it is noted that reduction between problems of functional complexity classes are defined as follows:
Function problem A reduces to ...
- 21
2
votes
0
answers
41
views
Statements equivalent to strongly polynomial time linear programming
Say a problem is SPT iff it admits an SPT algorithm. What statements of interest are known to be equivalent to "LP is SPT"? Examples:
"linear feasibility solving is SPT" (due to ...
- 672
1
vote
0
answers
66
views
Reduction from unweighted graphs to weighted graphs?
Are there any examples where you take a problem for the unweighted case and reduce it to the weighted case? (Not the other way around).
My objective is to do something similar to the following: If the ...
0
votes
0
answers
87
views
Existence of W[1]-Hard construction from multiple hard problems
I am a research scholar working on parameterized complexity. Currently, I am exploring ways to prove the hardness of a problem by providing W[1]-Hard constructions. A problem is known to be fixed-...
6
votes
1
answer
319
views
Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82
I was reading the paper "Optimal Algorithms for Approximate Clustering", Feder and Greene [1988] (https://dl.acm.org/doi/10.1145/62212.62255).
Specifically, I was trying to look at the $1.82$...
- 43
1
vote
1
answer
104
views
What is region construction in timed automata?
I've recently started self-learning timed automata.
There's this theorem in there that a timed automaton can be converted to a DFA using a "region" construction. I've looked up references on ...
- 135
2
votes
0
answers
136
views
Complexity of a sum with a product
Is the following problem NP-complete:
Input: A set of tuples $T = \left\{ t_i=(a_i,b_i) | 1\le i\le n \right\}$, an integer $k$ and numbers $C,D\in \mathbb Q_{\ge 0}$.
Question: Exists a subset $S\...
- 81
-1
votes
1
answer
111
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.
- 111
-1
votes
1
answer
139
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 ...
- 109
0
votes
1
answer
208
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 ...
- 1,029
4
votes
0
answers
98
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 ...
- 193
12
votes
0
answers
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 ...
- 7,590
-1
votes
1
answer
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)$...
- 89
3
votes
0
answers
106
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 ...
- 193
6
votes
1
answer
267
views
Complexity of reachability in directed rooted forests
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 $...
- 133
1
vote
0
answers
148
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 ...
- 111
1
vote
1
answer
248
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 ...
- 11
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)...
- 31
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(...
- 498
2
votes
2
answers
411
views
Proving not NP-complete by non-existence of gadget
Suppose we suspect a problem to be polynomial time solvable, but we are unable to prove this. So, we attempt to prove that the problem cannot be NP-hard. Known proofs in this direction show that if ...
- 1,827
5
votes
0
answers
68
views
The complexity of tensor formula evaluation problem over an infinite field
In the paper The complexity of tensor calculus by C. Damm, M. Holzer and P. McKenzie (link), the authors reduced the problem of computing the permanent of 0/1-matrices to that of evaluating tensor ...
- 81
4
votes
0
answers
182
views
The graph of problem reductions
A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature ...
- 693
0
votes
2
answers
209
views
Knowing if there are two solutions to the subset sum problem
I was wondering if there are any results that say how hard it is to answer the question are there TWO subsets that sum to a fixed value? In other words, the subset sum problem but asking if there are ...
- 119
7
votes
1
answer
356
views
Is solving the following system of boolean equations NP-hard?
I reduced a problem I'm currently working on to the following system of boolean equations:
$$
X_i \iff
\begin{cases}
\bigvee_{B \in A_i} \bigwedge_{k \in B} X_k \\
true \\
false
\end{cases}
$$
Where $|...
- 173
1
vote
0
answers
77
views
Some examples of tools to demonstrate problem is in $NC$ [closed]
Unlike the class $P$ or $NP$ the class $NC$ does not have any complete problems. To show a problem is in $NC$ one needs to marshal efforts to directly show the problem is in $NC$ since there are no ...
- 13.1k
0
votes
0
answers
207
views
3-partition problem without the restriction to triplets
In the standard 3-partition problem, there are $3 m$ integers, their sum is $m T$, and they have to be partitioned into $m$ subsets of sum $T$ and size $3$.
Consider the variant without the ...
- 2,294