Skip to main content

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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
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: ...
5 votes
1 answer
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. ...
0 votes
0 answers
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.
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 ...
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 ...
-4 votes
1 answer
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 ...
36 votes
6 answers
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 ...
0 votes
1 answer
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
0 answers
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 ...
0 votes
0 answers
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 ...
7 votes
2 answers
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 ...
0 votes
2 answers
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 ...
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 ...
16 votes
3 answers
5k views

Subset sum vs. Subset product (strong vs. weak NP hardness)

I was hoping that some one might be able to explain to me why exactly the subset product problem is strongly NP-hard while the subset sum problem is weakly NP-hard. Subset Sum: Given $X = \{x_1,...,...
4 votes
1 answer
223 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 ...
2 votes
1 answer
91 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. ...
0 votes
0 answers
97 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 ...
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 ...
6 votes
0 answers
177 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-...
11 votes
1 answer
220 views

$\mathsf{TC^0}$-completeness and reductions

AFAIU, we don't know any problem which is complete for $\mathsf{TC^0}$ w.r.t. many-one $\mathsf{AC^0}$ reductions ($\leq^\mathsf{AC^0}_m$). On the other hand, proving that they don't exist would ...
7 votes
1 answer
217 views

Is Circuit Minimization $P$-hard under logspace reductions?

By Circuit Minimization, I am referring to the following decision problem. Circuit Minimization Input: A bit string $x$ and a number $k$. Question: Does there exist a Boolean Circuit $C$...
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, ...
3 votes
0 answers
86 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 ...
1 vote
0 answers
77 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,...
5 votes
1 answer
76 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^...
2 votes
0 answers
117 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?
4 votes
2 answers
452 views

Random self reducibility and NP

I was reading the Wikipedia page Random self-reducibility and it states: If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy collapses to $\Sigma_3$. I am ...
9 votes
1 answer
172 views

What is known about reduction by "$P_1$ interprets $P_2$" for generalized programming languages?

Inspired by this answer, let's say that a programming language is given by the data $L=(P,ev)$ where $P$ (the set of "valid programs") is a computable subset of $\Sigma^*$ and $ev$ (the "evaluator") ...
6 votes
1 answer
316 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$...
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 ...
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 ...
1 vote
0 answers
63 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 ...
15 votes
1 answer
952 views

Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
0 votes
0 answers
83 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-...
1 vote
1 answer
96 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 ...
2 votes
0 answers
134 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\...
-1 votes
1 answer
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.
-1 votes
1 answer
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 ...
3 votes
1 answer
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....
0 votes
1 answer
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 ...
4 votes
0 answers
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 ...
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 ...
-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)$...
3 votes
0 answers
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
1 answer
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 ...
6 votes
1 answer
264 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 $...
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(...
9 votes
1 answer
350 views

Existing implementation of Scott's reduction?

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

1
2 3 4 5