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

1,123 questions
Filter by
Sorted by
Tagged with
26 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 ...
69 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 ...
45 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 ...
21 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 ...
5 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$ ...
61 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 ...
36 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?
36 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 ...
19 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 ...