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
1
vote
1answer
68 views

Turing reducibility of 2 versions of the satisfiability problem

I need help with this problem. There are 2 versions of the satisfiability problem: [1] decision version: determine whether an arbitrary formula f is satisfiable or not [2] search ...
2
votes
1answer
30 views

NPC PROBLEM minimum sum of vertex coloring

For a graph G and a legal vertex-colouring ψ : V(G)→N of G, let σψ(G) be the sum of ψ(v), and set σ(G):=min σψ(G), where the minimum ranges over all valid vertex colourings of G. Prove that {(...
0
votes
1answer
111 views

A non-polynomial reduction

Given two problems $P_1$ and $P_2$. $P_1$ is NP-complete in the strong sense and we want to prove that $P_2$ is also NP-complete but the reduction from $P_1$ to $P_2$ is not polynomial. Can we say ...
1
vote
1answer
109 views

Karp reduction from optimization problems to decision problems

When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other. Focusing on Cook reductions, there exists a natural Karp ...
1
vote
0answers
81 views

Prove that $\#k-colouring$ graph problem is $\#P-complete$

I need to prove, that the $\#k-colouring$ graph problem is $\#P-complete$. I want to construct the reduction from $\#3SAT$ problem, so $\#3SAT \leq \#k-colouring$. The reduction between the counting ...
16
votes
2answers
3k views

Poly-time reduction from ILP to SAT?

So, as is known, ILP's 0-1 decision problem is NP-complete. Showing it's in NP is easy, and the original reduction was from SAT; since then, many other NP-Complete problems have been shown to have ILP ...
2
votes
1answer
99 views

Scheduling to minimize the truncated gaps

I have a single job of unit length, a set of $n$ slots, and a budget of $B$ units. If the job is scheduled at slot $t$, then it will consume $c(t)$ units of the budget $B$. If the job is not scheduled ...
0
votes
0answers
21 views

Computing Every Path from a Source to Multiple Destinations [Simpler Algorithm]

How are these two problems different? I. Find all paths between a source vertex and destination vertex. II. Find all paths between a source vertex and all vertices in the graph. Both of these ...
1
vote
1answer
820 views

Reduction from 3-SAT to a graph problem

I have a question, i was trying to reduce 3-SAT to a particular graph problem and i'm not quite sure about a thing i used in the reduction. In fact the reduction build a bipartite graph, the edge $(...
4
votes
3answers
2k views

Reduce Vertex Cover with size k to Vertex Cover with size n/2

Disclaimer: This is a homework question. I would like to reduce vertex cover problem to the following problem: $$L = \{G \mid G\text{ has a vertex cover of size } |V(G)|/2\}\,.$$ I have divided the ...
1
vote
1answer
157 views

How can we know if a Turing machine halts, given that it writes to finite memory?

I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine 𝑀 writes to an arbitrary amount of memory, and false if it ...
1
vote
1answer
76 views

Turing machines: can a machine write to a finite number of memory cells, but not halt?

I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine $M$ writes to an arbitrary amount of memory, and false if it ...
3
votes
3answers
205 views

Has anyone seen a NP graph problem like this before?

I have a following graph-based problem: Input: positive integers K and L, undirected graph G I have to choose K vertices from this graph In the path between each pair of chosen K vertices there ...
0
votes
0answers
60 views

If a problem A ≤p B, then that B ≤p A, prove or disprove

I think the intuition is to disprove this by counter example, but what are 2 specific well known problems I can use as counter example?
1
vote
2answers
87 views

Is $\frac{n}{3}$-CLIQUE NP-complete?

Consider the problem $\frac{n}{3}$-CLIQUE: determining whether a graph contains a clique with at least $n/3$ vertices. I want to prove it is NP-complete using a polynomial transformation from CLIQUE. ...
3
votes
1answer
110 views

Is the knapsack problem NP-hard when $v_i=i$?

The knapsack problem is NP-hard and can be formulated as: $$\begin{align}&\text{maximize } \sum_{i=1}^n v_i x_i,\tag{P1}\\& \text{subject to } \sum_{i=1}^n w_i x_i \leq W,\\&\text{and } ...
0
votes
2answers
379 views

Reducing Vertex Cover to Half Vertex Cover

I need to reduce Vertex Cover to Half Vertex Cover using a Karp reduction: Vertex Cover: Given a graph $G = (V,E)$ and an integer $k$, is there a subset of $V$ of size $k$ which intersects all edges? ...
1
vote
1answer
241 views

Turing reducible in natural numbers?

I'm confused about Turing reducible things. I understanded Turing reducible like this ...
2
votes
0answers
32 views

Reducing Kleene's predecessor for Church numerals

I am trying to "reinvent" Kleene's predecessor myself. The following code snippet should be self-explanatory. The idea is to make a 2-tuple and count up from zero, i.e. ...
3
votes
2answers
724 views

Is this problem NP-hard? Maximizing selected sets so that their union is less than k?

There is an NP-hard problem called Minimum k-Union where we are given a set system with $n$ sets and are asked to select $k$ sets in order to minimize the size of their union. I'm currently ...
0
votes
0answers
31 views

Find decidable sets such that $A$ reduces to $B$ but not vice versa

I am stuck in this problem, so any help is appreciated. The problem asks to show that there exists decidable sets $A$ and $B$ such that $A \leq_{m}^{p} B$ but $B \not \leq_{m}^{p} A$, and that $A$, $B$...
1
vote
1answer
140 views

Proving undecidability of HALT_tm by reduction

Sipser in his book introduction to the theory of computation provided a proof of undecidability of $HALT_{TM}$. He uses a contradiction, he assumed that $HALT_{TM}$ ...
2
votes
1answer
30 views

Reductions to and from PRIME

I think PRIME (is the given number a prime number?) is a good example a decision problem. Therefore, when I'm trying to explain reduction, I'd like to give an example of a problem that is related to ...
1
vote
1answer
19 views

Equivalence between MIN UNCUT and MIN-CSP_XOR

In this paper Agarwal, Amit, et al. "O (√ log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems." Proceedings of the thirty-seventh annual ACM symposium on ...
20
votes
2answers
4k views

Can one show NP-hardness by Turing reductions?

In the paper Complexity of the Frobenius Problem by Ramírez-Alfonsín, a problem was proved to be NP-complete using Turing reductions. Is that possible? How exactly? I thought this was only possible by ...
2
votes
1answer
76 views

How to prove the NP-completeness of MOD-PARTITION

MOD-PARTITION: Given a set of integers $A={a_1,...,a_n}$, their weights $w = \{w_1, w_2, \dots, w_n\}$ and the number $k$, does there exist a subset $X$ of $A$ such that: $(\sum_{x \in X} w(x) * x) \...
8
votes
4answers
4k views

How are all NP Complete problems similar?

I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps. Prove that current problem is NP, i.e., given a certificate, prove that it can be verified ...
0
votes
1answer
232 views

pseudo-polynomial reduction from 3-Partition to Partition

A problem $\Pi'$ is pseudo-polynomially reducible to the problem $\Pi$ ($\Pi' \leq_{pp} \Pi$) if, for any instance $I'$ of $\Pi'$, an instance $I$ of $Π$ can be constructed in pseudo-polynomially ...
3
votes
0answers
39 views

Standardisation Theorem versus Leftmost reduction Theorem

According to Chris Hankin in his book (Lambda Calculus a Guide for Computer Scientists). A reduction sequence $\sigma: M_0 \to^{\Delta_0} M_1 \to^{\Delta_1}M_2 \to^{\Delta_2}\ldots $ is a standard ...
2
votes
0answers
45 views

Why can the construction of a polynomial-sized structure be done in logspace?

In paper http://www.iro.umontreal.ca/~mckenzie/Recherche/homc10fun.pdf the authors prove their problem is NL-complete. At some point in their proof however, they construct a polynomial-sized graph, ...
2
votes
1answer
185 views

Hardness of a scheduling/assignment problem

I am trying to prove the hardness of the following problem. This problem is from google hashcode, qualification-round, 2020. Hier is a brief description of the problem. Given a list or libraries and ...
12
votes
1answer
220 views

Are there any known AM-complete problems/is AM-complete well defined?

I'm curious about whether there are any complete problems in the Arthur-Merlin complexity class. Graph Non-Isomorphism (GNI) seems to be the canonical example of a problem in AM, but it's probably not ...
0
votes
2answers
91 views

IS there a consensus on the definition of a computer program in CS literature and if so, what is it?

The following is what I came up with from my synthetic prior research but I might be wrong. I understand it is possible to reduce any computer "program", in a maximal reduction(?), to these features: ...
4
votes
1answer
353 views

Two versions of Subset Sum Problem

I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is: Given an integer bound $W$ and a collection of $n$ items, each with a positive integer weight $w_i$, ...
0
votes
1answer
23 views

Reducing vertex cover to minimal vertex cover

What is a quick and a elegant way to reduce vertex cover to minimal vertex cover? Is it possible to use vertex cover as verifier in the algorithm that reduces vertex cover to minimal vertex cover? ...
2
votes
2answers
2k views

Does showing a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?

I was reading the Sipser's book on the Theory of Computation, 3rd edition and came up with a question. "Does showing a problem and its complement are not Turing-decidable means that the language & ...
5
votes
2answers
3k views

Optimization problem vs decision problem - reduction

Assume we have an optimization problem with function $f$ to maximize. Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to ...
1
vote
1answer
55 views

Proving that the set of grammars generating L or L complement is undecidable

Let $X$ be a regular language, I need to prove that either $\{G \mid L(G) = X\}$ or $\{G \mid L(G) = \overline{X} \}$ is undecidable using the following hint: Use reduction to absurdity supposing that ...
0
votes
2answers
2k views

How can one reduce 3-CNF-SAT and k-CNF-SAT to each other?

I am studying for NP problems. To prove k-CNF-SAT is NP-hard, there must exists something that can be reduced to k-CNF-SAT. So what I thought is to reduce 3-CNF-SAT to k-CNF-SAT and reduce k-CNF-SAT ...
1
vote
1answer
131 views

Reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} $

How to reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} =\{\langle M,w \rangle: M$ is a Turing machine that accepts $w$}. My try: Construct a ...
4
votes
1answer
116 views

why does $ A≤_p \#SAT$ if $A \in BPP$

hello and thank you for helping me understand the following: I really don't understand this, why if language $A \in BPP$ then $A≤_P\#SAT$? language A is in BPP class, if for a probabilistic turing ...
0
votes
1answer
83 views

Is L decidable or not

Let $L = \{\lt M\gt | M$ is a $TM, L(M) = \{1^n0^n | n\ge0\}\}$. Create a reduction from $A_{TM}$ (acceptance problem) to $L$. Is $L$ not decidable? But isn't $L$ decidable since it is possible to ...
3
votes
1answer
72 views

Is the following fuction computable?

I'm trying to show that $K_1 \le_1 K$ where $K$ is the diagonal halting set $\{x : \varphi_x(x) \downarrow\}$ and $K_1=\{x: \exists y \,\, \varphi_x(y) \downarrow\}$, then I defined the function $$\...
29
votes
1answer
898 views

Graph problem known to be $NP$-complete only under Cook reduction

The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a ...
1
vote
2answers
62 views

Is the number of NP-complete problems finite?

It should be straight forward to show that there are infinitely many NP-hard problems: Proof: Take the problem Remove 1 Vertex 3-COL ($R1V3COL$) which takes a graph $G=(V,E)$ as an instance and ...
-1
votes
1answer
36 views

if there is no reduction from A to B

I'm facing the following question : If there is no $𝐴\leq_𝑚𝐵$ reduction, does this necessarily mean that A is not decidable? for any choice of B. thanks in advance.
0
votes
1answer
61 views

What is the result of a reduction operation called?

Is there a commonly used term for the result of a reduction operation? "reductant" does not quite sound right...
2
votes
1answer
233 views

Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?

Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k) polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a ...
3
votes
1answer
388 views

Undecidability of two Turing machines acting the same way on an input

So I need to find a reduction to the (undecidable) problem of deciding if two Turing machines $M_1$ and $M_2$ behave the same way on an input $x$. "Behaving the same way" is defined like this: $M_1$ ...
1
vote
1answer
360 views

Is Finding A Hitting Set of Size n/2 NP-Hard?

In Hitting Set problem we are given a collection E of subsets of V and we want to find smallest subset H of V which intersects (hits) every set in E. In decision version of the problem, we are asked ...

1
3 4
5
6 7
23