Questions tagged [reductions]

In computability and complexity, finding mappings between problems that allow solving one problem using a solution of another one. For reduction in programming language theory (e.g. beta-reduction), see [lambda-calculus] or [term-rewriting].

Filter by
Sorted by
Tagged with
0
votes
0answers
22 views

If $L_1 \leq_m L_2$, and $L_2$ is decidable, is $L_1$ then decidable?

There is a lemma in our textbook that asks us to prove the following: If $L_1 \leq_m L_2$, and $L_2$ is decidable, then $L_1$ is decidable I tried proving this by saying that if $L_1 \leq_m L_2$, ...
0
votes
1answer
28 views

reduction from 3SUM to 3ARR-ARITH

The 3SUM problem is defined as follows. Given an array A[1...n] of numbers, determine whether there exist $i,j,k\in \{1,\cdots, n\}$ so that $A[i] + A[j]+A[k] = 0$. The 3ARR-ARITH problem is defined ...
1
vote
1answer
24 views

Reducing a CNF formula to a DNF formula in less than exponential time

The easy way is by looking at the $\{0,1\}$-table and construct the corresponding DNF formula from that, but this will take $2^n$ time. I want to do it much more efficiently. My idea is based upon the ...
4
votes
1answer
66 views

Attempt to reduce to problem of inner product

The problem of Orthogonality: gives $n$ vectors of dimension $k$ and another set of same, can a pair be found with inner product = $0$? The problem of max product: likewise two sets each $n$ vectors (...
0
votes
0answers
19 views

Reduction from SAT to EXACTSAT

PROBLEM: EXACTSAT INPUT: A boolean formula $\phi$ in CNF with $n$ variables, and a natural number $k \le n$. OUTPUT: "Yes" if and only if there is truth assignment $\theta$ which sets ...
0
votes
0answers
39 views

In-place Acceptance Problem

In-place Acceptance Problem (InAP) Instance: A deterministic Turing Machine M and a w input for it. Question: Does M accept the input w without going through cell (|w|+1)? Show that InAP is PSPACE-...
1
vote
1answer
20 views

Can I reduce from the recognition version of one probem to another without knowing the exact parameter?

I was reading the paper "Kou, L. T., Stockmeyer, L. J., & Wong, C. K. (1978). Covering edges by cliques with regard to keyword conflicts and intersection graphs. Communications of the ACM, 21(...
0
votes
1answer
29 views

Help in proving L-Completeness

I'm trying to prove that the following language is L-complete A is a language where each word is comprised of 0s and 1s & the number of 0's is double that of the number of 1's So far I've managed ...
2
votes
1answer
189 views

How to reduce SUBSET-SUM with integers to SUBSET-SUM with non-negative integers?

The subset sum problem is as follows: Given a sequence of integers $\mathcal S=(a_1, ..., a_n)$ with cardinality $n$ and an integer $T$, determine whether there is a subsequence of $\mathcal S$ whose ...
2
votes
0answers
31 views

Non-trivial reduction form SAT to $3$-SAT

Looking for any idea for reduction from $SAT \leq 3-SAT$ where $SAT$ is known to have $d$ variables at most in each clause. I am looking for a reduction in which the resulting formula will not depend ...
2
votes
1answer
11 views

Question on worst-to-average-case reductions

Consider two decision problems A and B. We know that A reduces to B in polynomial time --- if we could solve B, we have a procedure to solve A. Now, let's say it is known that the worst case instances ...
1
vote
0answers
34 views

Hitting set problem and Vertex Cover

In Chapter 8 Question 5 of Kleinberg and Tardos, the problem is as follows: Consider a set $A = \{a_1, \ldots , a_n\}$ and a collection $B_1, B_2, \ldots , B_m$ of subsets of $A$ (i.e., $B_i \...
0
votes
1answer
36 views

How can we prove that a reduction exists?

Problem: I have two computational problems, $A$ and $B$. We know that $A \in \texttt{Psearch}$ and I want to prove that $A \leq_p B$ for all problems $B$. Goal: It is my understanding that my goal is ...
0
votes
1answer
39 views

chromatic number is np-hard

I'm referring to a question in this book: Algorithms by Jeff Erickson, link:http://jeffe.cs.illinois.edu/teaching/algorithms/notes/J-approx.pdf, in particular, pg.21, Q11. The author mentioned that ...
1
vote
0answers
22 views

Relationship between complexity classes W[1]-hard and NP-hard?

If i have a parameterized reduction from multicolored independent set (W[$1$]-hard) to some problem $A$, which take polynomial time. Can i say that problem $A$ is NP-hard? in other words, Is ...
0
votes
0answers
20 views

Strategy to reduce between decision problems

I'm very new to complexity theory, please help me fill in the gaps in whatever knowledge I have acquired till now. A decision problem is a problem $X(D)$ that outputs for each input instance $I$, a ...
0
votes
0answers
33 views

Reduction techniques in complexity

I am learning computational complexity and parameter complexity. In order to proof that a problem is np-hard, we should reduction one which is np-hard to the problem. However, I don't have any idea ...
2
votes
2answers
48 views

Problem reduction: Can YES-Instances also be mapped to NO-Instances if there is perfect correspondence?

Definition: Problem A is reducible to problem B if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently. When this is true, ...
1
vote
0answers
44 views

Simple example of LogSpace reduction

In general, how can I verify that my many-one reduction is a LogSpace reduction? E.g. I was looking at the proof of HORN-SAT is P-complete via logspace reduction. It would be ok even if someone makes ...
2
votes
2answers
174 views

Why can't I use a polynomial-time reduction for proving P-completeness?

According to the Wikipedia page on P-complete, a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate ...
0
votes
1answer
35 views

Algorithm to reduce a Circuit-SAT to NAND-SAT

I am trying to construct an algorithm to reduce OR, AND and NOT gates into NAND-SAT. Can someone give me a hint as to where to start?
-1
votes
1answer
28 views

If two languages are polytime reducable, does that imply they are also turing reducable

Is it possible for a pair of languages where A ≤T B but not A ≤p B? I am not sure if this could be the case since a turning reduction would imply we can use a decider for one language to decide ...
0
votes
1answer
30 views

Reduction: Does polytime reduction imply Turing reduction?

I am unsure if given $A \leqslant_p B$, does that imply that $A \leqslant_T B$. If we can polytime reduce $A$ to $B$, that would imply there is a decider for $A$ that runs in polynomial time which can ...
0
votes
1answer
17 views

Polytime Mapping Reduction from Language A to Language A (identity)

How would I create a polytime mapping reduction to prove A ≤p A for any language A. I was thinking to assume A is in P to start. For every 𝑥: 𝑥∈𝐴 iff 𝑓(𝑥)∈𝐴. But I am not sure what to do from ...
0
votes
1answer
36 views

NP-Completeness of SAT with given hamming weight k [duplicate]

I think that the following problem is NP-Complete but I don't have any idea of how doing the reduction. Input: A propositional formula $\varphi$ and a number $k$. Output: Yes if exists an valuation $\...
2
votes
2answers
30 views
1
vote
1answer
28 views

What class is the language $(C,(v_i)_{i=1}^m,x)$ complete to s.t. $C(x)$ is a boolean circuit with $m$ gates with values $\{v_i\}_{i=1}^m$

Given the following language: $$ L=\left\{\,(\,C,\,\{v_i\}_{i=1}^m, \,x\,) \enspace :\enspace \substack{C(x) \text{ is a boolean circuit with } m \text{ gates} \\i\text{'th gate value is } v_i \text{...
0
votes
1answer
51 views

Reduction of RE and Rec languages

Suppose $L_1$ is reduces to $L_2$ in polynomial time, $L_1\leq_p^\mathsf{}L_2.$ we know that if $L_2$ is RE then $L_1$ is also RE and $L_2$ is REC then $L_1$ is also REC. And also I know that if $...
1
vote
1answer
36 views

Can one show NP-completeness by showing a reduction to 3SAT?

The standard technique to show NP-completeness of $L$ seems to be to show that $L$ is in NP, and then to show that some NP-complete language can be reduced to it. What if one tried to show it the ...
3
votes
1answer
72 views

Is there a book with 100 reductions?

In a lecture I'm taking about complexity theory a professor said, there are infinite many NP-complete problems. Question: I was wondering if there exists something like a database or a book with some ...
0
votes
1answer
64 views

Reduction from recursive language to recursive enumerable

If any language $L_1$ reduces $L_2$ in polynomial time $L_1\leq_p^\mathsf{}L_2.$ If $L_1$ is recursive then $L_2$ is recursive and recursively enumerable, is it true? Because $L_2$ is at least as ...
0
votes
0answers
26 views

Given a graph and specific VC instance, find number of variables when reducing from VC to SAT

I have question already answered from past exam, and I'm trying to figure where my logic fails. Given a graph find vertex cover of size 2. The question is how many variables are there going to be for ...
0
votes
0answers
7 views

Are Path-systems P-complete under logspace many-one reductions?

As far as I know, the admissability of a path-system is an example of a P-complete problem. However, I am not sure under which kind of reductions (many-one or turing-reductions? logspace or AC$^0$ ...
1
vote
1answer
82 views

Reduction of K-Vertex-Cover to SAT: How to define the constraint?

Overall, one would naturally think that with n different nodes, and for x(1) for example representing node 1, it would be like: x(1)+x(2)+x(3)...+x(n) <= k This would mean that for every possible ...
1
vote
1answer
56 views

How to convert Bipartite Perfect Matching to SAT?

SAT is $NP$-complete while Bipartite Perfect Matching is in NC under derandomization assumptions. How to convert Bipartite Perfect Matching from balanced bipartites to SAT without Cook-Levin?
1
vote
1answer
37 views

Language classification

I am currently taking a computational course as part of my degree in Computer Science, and I would like to understand in depth the differences between these languages and if their belonging to R. The ...
0
votes
1answer
25 views

Mapping reduction properties exercise

I am having trouble understanding how to conclude if the statements are true or false, I would really appreciate your help. We know about three languages, A, B and C. There exists a mapping reduction ...
1
vote
0answers
25 views

How to reduce $\overline{K} \leq L$, or how to show semi-decidability of a given language?

I'm currently preparing for an exam and I'm having trouble to solve the following Questions. Let $w \in \{0,1\}^*$ and let $L$ be a language defined as follows $$L = \{w \mid \mathsf{time}_{M_w}(x) \...
0
votes
1answer
31 views

If problem A reduces to an NP-Complete problem B, can we say that A is in NP?

I was reviewing All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete? I understand that the general way we show a problem A is in NP is to show there exists a poly-...
-2
votes
2answers
52 views

Is A and C NP-complete?

Given 3 decision problems in $NP$: $A,B,C$. Consider that there are $2$ reduction algorithms, one is $A\le_p B$ (with run-time $n^{10}$) and the other is $B\le_p C$ (with run-time $n^5$). If $B$ is $...
0
votes
0answers
35 views

Is there a reduction from 2sat to bpm?

Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?
1
vote
1answer
31 views

Question about Turing and Many-One Reductions

I have seen this statement in my studies and I cannot figure out why it is true. We know that $P_{HALT} \leq_T \overline{P_{HALT}}$, but $P_{HALT} \leq_m \overline{P_{HALT}}$ does not hold. I know, ...
0
votes
0answers
42 views

Reduction from Edge-Coloring and Vertex-Coloring to a new problem

I have a question from a test I did and failed, a question I failed to do. In short: the question is about reduction from Vertex-coloring and Edge-coloring, to a new problem they have defined. The new ...
-1
votes
1answer
80 views

Reduction from problem A to another problem B

I have a question from a test that I failed to pass, I failed to do the question. The question: Let A and B have two languages so that there is a reduction function f: $A\leq _pB$. Suppose that $A \in ...
0
votes
2answers
105 views

Reduction between CLIQUE to SUBSET SUM

I have a question from a test that I failed to pass, I failed to do the question. The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the ...
0
votes
1answer
42 views

Reduction from language in P to another language in NP

I have a question I was unable to do, from a last test I had. This is the question: Will be $A \in NP$ Let $c \in P$ be a language so that there exists $C \leq _pA$. Determine which of the following ...
3
votes
1answer
111 views

Reduction from the SAT problem to the NAE-SAT problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: For the SAT problem, there is a version in which we receive as input phrase $\varphi$ in ...
0
votes
2answers
175 views

edge-coloring and vertex-coloring reduction problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: Edge-Coloring problem, we get as input graph G = (V, E) and natural number k and ask "...
0
votes
1answer
40 views

Reduction from the Clique problem to the Odd Clique problem

I have a question that is not clear to me, and I have not been able to answer it from a test I had. This is the question: Let's look at the problem $Oclique$ , In it we get a graph $G = (V,E)$ , And ...
0
votes
1answer
33 views

Complications of a language that reaches a state of reject

I have a question that is not clear to me, and I have not been able to answer it from a test I had. This is the question Let's look at the language $L_\mathrm{reject} = ${ $\left \langle M,w \right \...

1
2 3 4 5
23