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 a undecidable problem. If this can be achieved ...

learn more… | top users | synonyms

-2
votes
0answers
27 views

Applying Tseitin Transformation to multi-output combinational circuit

I needed help with transforming multiple output combinational circuit to CNF sub-expressions using Tseitin transformation.I am a beginner in this field and also unable to find any resources online. ...
0
votes
0answers
25 views

L-reduction From Matrix-Tiling To Minimal Dominating Set in Unit Disk Graph

Recently I read this paper which was published in FOCS2007. In section 4, just before Theorem 4.2, the author mentioned that the gadget construction of Minimum Dominating Set in UDG is similar to ...
2
votes
1answer
229 views

Is there a FNP problem that's NP-hard but not FNP-hard?

For the reductions, choose a class C such that [it's clear what FC means] and FC is not known to be able to solve the satisfaction search problem, and assume that FC indeed can't solve that search ...
0
votes
0answers
44 views

Generalized caching Problem offline version

statement 1: Here we are given a cache of size k and pages with arbitrary sizes and fetching costs. Given a request sequence of pages, the goal is to minimize the total cost of fetching the pages ...
4
votes
0answers
74 views

Is anything known about Sokoban with only 1 box?

This is intended to be a simpler version of my earlier question here. In this post, 1-Sokoban-search is Sokoban with only 1 box, 1-Sokoban-decision is the corresponding decision problem, and ...
7
votes
1answer
154 views

Improving Cook's generic reduction for Clique to SAT?

I am interested in reducing $k$-Clique to SAT without making the instance much larger. Clique is in NP so it can be reduced to SAT using logarithmic space. The straightforward Garey/Johnson textbook ...
1
vote
1answer
81 views

Polynomial-time reductions between undecidable languages

The Turing degree $\mathbf{0}'$ is defined as all languages Turing-equivalent to the halting problem. In fact any recursively enumerable language is polynomial-time reducible to the halting problem. ...
11
votes
1answer
198 views

Slowest many-one reduction?

When we want to prove that an $L\in \bf NP$ is $\bf NP$-complete, then the standard approach is to exhibit a polynomial time computable many-one reduction of a known $\bf NP$-complete problem to $L$. ...
11
votes
1answer
223 views

Sampling a uniformly random satisfying assignment

Problem: Given $\phi : \{0,1\}^n \to \{0,1\}$ represented by a boolean circuit, generate a uniformly random $x \in \{0,1\}^n$ such that $\phi(x)=1$ (or output $\perp$ if no such $x$ exists). ...
4
votes
1answer
82 views

NP-Complete Convergent Reductions?

A professor I knew in grad school told me about asking his students to reduce an NP-Complete problem to another, then back to the original, then back again and then watching with amusement as the ...
9
votes
0answers
92 views

Is it possible to boost the error probability of a Consensus protocol over dynamic network?

Consider the binary consensus problem in a synchronous setting over dynamic network (thus, there are $n$ nodes, and some of them are connected by edges that may change round to round). Given a ...
12
votes
1answer
353 views

Which complexity class does this number theory problem belong to?

'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by=c$' is $\mathsf{NP}$-complete. Which complexity class does 'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by^2=c$' belong to?
7
votes
1answer
160 views

Limited number of variable occurrences in 1-in-3 SAT

Is there a known result on complexity class of 1-in-3-SAT with restricted number of variable occurrences? I've come up with the following parsimonious reduction with Peter Nightingale, but I want ...
-1
votes
1answer
104 views

Will a non-linear lower bound on some NP complete problem prove non-linear lower bound on 3SAT?

A problem $\Pi$ is $\mathsf{NP}$ complete if there is a polynomial time reduction from an $\mathsf{NP}$ complete problem $\Pi^\circ$ to $\Pi$ with polynomial blow up on number of variables and ...
0
votes
0answers
28 views

Claw finding algorithm transformation

In Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies by DeFeo, Jao and Plut (PDF) there is a quantum-resistant cryptosystem defined. On page 17/18 is a quantum attack ...
19
votes
1answer
403 views

How to prove that USTCONN requires logarithmic space?

USTCONN is the problem that requires deciding whether there is a path from the source vertex $s$ to the target vertex $t$ in a graph $G$, where these are all given as part of the input. Omer Reingold ...
3
votes
0answers
168 views

PSPACE completeness, with different kinds of reductions

PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction, i.e. the reduction is an algorithm $\in$ FP. ...
5
votes
1answer
178 views

Reducing sorting to max-flow

Is there a linear-time reduction from the sorting problem to the max-flow problem? If so, what would such a reduction look like?
6
votes
2answers
363 views

Proof for Kolmogorov complexity is uncomputable using reductions

I am looking for a proof that Kolmogorov complexity is uncomputable using a reduction from another uncomputable problem. The common proof is a formalization of Berry's paradox rather than a reduction, ...
0
votes
0answers
79 views

Is this some variant of the Knapsack Problem?

We are a set of items $I = \{I_1, I_2,.. I_n\}$, which need to be placed in a certain number of knapsacks $K$. We can use as many knapsacks as we want and each knapsack has an infinite capacity but ...
2
votes
0answers
117 views

Complexity of Knapsack-type problem with applications to computational workflows

Consider the following problem: Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...
3
votes
1answer
218 views

#P- vs PP-Completeness

Suppose $A$ is any #P-complete problem. Now, $A$ is modified to obtain a decision problem $A'$ not by asking whether there is a solution but whether at least half of the potential solutions are ...
0
votes
0answers
108 views

Is there a reduction from a 0-1 knapsack problem to the unbounded problem?

As we know, an unbounded knapsack problem could be described as: $\max \sum_{i=1}^nc_1x_i$ s.t. $\sum_{i=1}^na_ix_i\le b$ $x_i\ge0,x_i\in\mathbb Z,i=1,\cdots,n$ And for an 0-1 knapsack problem, we ...
6
votes
1answer
80 views

Does learning conjunctions with malicious noise reduce to learning conjunctions with random noise?

In Feldman-Gopalan-Khot-Ponnuswami 06 the authors show that agnostically learning parities reduces to learning parities with random classification noise. They also remark (among other things) that ...
23
votes
1answer
611 views

Are there subexponential algorithms for PLANAR SAT known?

Some NP-hard problems which are exponential on general graphs are subexponential on planar graphs because the treewidth is at most $4.9 \sqrt{|V(G)|}$ and they are exponential in the treewidth. ...
4
votes
1answer
212 views

Reduction SAT to a problem on a planar graph with as few vertices as possible

Let $\phi$ be CNF formula with $n$ variables and $m$ clauses. I am looking for a reduction is $\phi$ satisfiable to a problem on a planar graph $G$ with as few vertices as possible. The majority of ...
2
votes
0answers
72 views

Introduction to Black-Box Separations in Cryptography

Are there any textbook-style material on black-box separations in cryptography? I tried to read the paper of Impagliazzo and Rudich but couldn't get much of it. A previous StackExchange entry gives a ...
0
votes
1answer
143 views

Many-one reduction from inequality problem to equality problem

Let the k-inequality-MIS problem be the decision problem whether an arbitrary graph $G=(V, E)$ contains a maximal independent set of at least size $k$, that is the corresponding language is: ...
20
votes
5answers
639 views

Curious about computer-assisted NP-completeness proofs

In the paper "THE COMPLEXITY OF SATISFIABILITY PROBLEMS" by Thomas J. Schaefer, the author has mentioned that ...
3
votes
1answer
123 views

The relationship between completeness and strength of reductions

Ladner theorem can be stated as: $P \ne NP$ if and only if there exists an incomplete set in $NP-P$. Here an incomplete set is a set that is not complete for $NP$ under many-one polynomial time ...
2
votes
2answers
196 views

Balls & Bins: A punishment and reward game

Consider a game where one has a set of bins $(b_1, b_2, ...)$, and each bin has an associated initial count of balls $(c_1, c_2, ...)$. The rules of the game are as follows: (1) Once a bin has a ...
7
votes
1answer
146 views

Minimal polynomial reduction of dominating set to max clique

Let $G$ be a simple undirected graph. Recall that $S \subseteq V(G)$ is a dominating set of $G$ if every vertex of $v \in V(G) \setminus S$ has a neighbour in $S.$ It is well known that it is NP ...
1
vote
0answers
75 views

Implication of lower bounds in Boolean circuit to other models of computation

Suppose that one can prove that some hard function $f$ with $n$ bit input does not admit any Boolean circuit of size at most $n^t$. Then, how strong can we say about how hard $f$ is in other models? ...
8
votes
1answer
194 views

Efficient Reduction from Min Cut to st-Min Cut

I am aware that many known algorithms for min cut problem is not by reducing the problem to $st$-min cut. But the question of efficient reduction from min cut to $st$-min cut is still interesting to ...
1
vote
1answer
254 views

Is there simple reduction Dominating Set to Vertex Cover?

Is there simple reduction Dominating Set to Vertex Cover? In the other direction the reduction is simple. Searching the web returned blog. It warns This is not finished yet and experiments ...
2
votes
1answer
122 views

Proof of an Ising model representation of graph isomorphism problem

I am going to through Ising formulations of many NP problems by Andrew Lucas. In section $9$ on page 22, the author introduced an exact Ising formulation of the graph isomorphism problem. Given two ...
6
votes
3answers
212 views

Solving problems by deciding a logic

I am curious to know when open problems have been solved by expressing them in a specific logic, and then showing that this logic is decidable. I have two distinct cases in mind: The problem is ...
7
votes
0answers
103 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") ...
3
votes
2answers
165 views

Root finding in [0,1]

I am interested in the problem of finding a real root of a polynomial equation $f(x)=0$ where $f(x)=\sum_{i=0}^n a_ix^i$. Is it possible to give a reduction, i.e, to compute a different polynomial $g$ ...
2
votes
0answers
140 views

Graph partition with objective over intra-partition weights

I have a problem in which I need to find an optimal graph cut that maximizes an objective over weights not on the cut. I have looked at the literature but have not been able to find any similar ...
0
votes
0answers
38 views

On Equivalence of “gen-CONF” problem and “DH-exp-inv” problem

Let $g$ be a generator of a group of prime order $p$; $a,b ∈_R Z_p^+$ Consider an Algorithm $\mathcal{A}$ which on input $g,g^a,g^{ab}$ outputs $g^{br},r$, for some non zero $r ∈ Z_p$ And an ...
7
votes
1answer
295 views

NP-hardness proof: looking for some good restricted np-hard problems

To show the NP-hardness of a problem, one need to choose a known NP-hard problem and find a polynomial reduction from the known problem to his problem in hand. Theoretically, any NP-hard problem can ...
13
votes
5answers
660 views

Should reductions make us more or less optimistic for the tractability of a problem?

It seems to me that most complexity theorists generally believe the following philosophical rule: If we can't figure out an efficient algorithm for problem $A$, and we can reduce problem $A$ to ...
3
votes
3answers
126 views

On proving it is hard to compute $g^{rb}$ with knowledge of $r$, given $g, g^a, g^{ab}$

I am trying to prove the following Given $g, g^a, g^{ab}$ it is hard to compute $r, g^r, g^{rb}$, for some arbitrarily chosen value of $r$ where $g ∈ \mathbb{G}, \mathbb{G}$ is a cyclic group ...
6
votes
1answer
371 views

Max-weight connected subgraph problem in planar graphs

The maximum-weight connected subgraph problem is as follows: Input: a graph $G=(V,E)$ and a weight $w_i$ (possibly negative) for each vertex $i \in V$. Output: a maximum-weight subset $S$ of ...
28
votes
7answers
1k views

Nontrivial membership in NP

Is there an example of a language which is in $NP$, but where we cannot prove this fact directly by showing that there exists a polynomial witness for membership in this language? Instead, the fact ...
13
votes
3answers
316 views

Can limit of hard languages be easy?

Can the following all hold simultaneously? $L_s$ is contained in $L_{s+1}$ for all positive integers $s$. $L = \bigcup_s L_s$ is the language of all finite words over $\{0,1\}$. There is some ...
13
votes
3answers
677 views

Transitive feedback arc set (TFAS): NP-complete?

Some time ago, I posted a reference request for graph problems where we want to find a 2-partition of the edges where both sets fulfill a property not related to their cardinality. I was trying to ...
9
votes
0answers
201 views

A reduction between small cliques problems

I'm looking for a reduction that gets a graph $G=(V_G,E_G)$ and outputs a graph $H$ that satisfies the following requirements. If $G$ contains a triangle, then $H$ contains a clique of size 9. If ...
3
votes
1answer
222 views

Maximize the expected number of “losers” - Is it NP-hard?

I am trying to find a reduction for a problem that seems NP-hard: Let me start from a toy example. Consider 3 elements, $a$, $b$, and $c$. You want to choose two pairs out of the three pairs and ...