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
0
votes
0
answers
29
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
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.
...
- 2,294
0
votes
0
answers
70
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
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 ...
- 101
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 ...
- 159
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 ...
- 181
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 ...
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 ...
- 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 ...
- 821
4
votes
1
answer
225
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
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 ...
- 135
2
votes
1
answer
92
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
98
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