# 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,186 questions
Filter by
Sorted by
Tagged with
20 views

### TSP given a length oracle

Consider given a code $C$ that takes as input an edge-weighted graph $((V,E), w)$ and returns the weight of the shortest path that traverses all nodes. How is the minimal number of invocations of $C$ ...
• 1
1 vote
55 views

8 views

### Is it possible to define logspace reductions with FO[TC] queries?

Assume that we have a NP problem A, and a NP-complete problem B under logspace reductions. Furthermore, lets assume that we encode the problem A into a relational database $D_A$, and B into another ...
• 317
1 vote
47 views

### $\mathrm{MON} = \{\langle M\rangle : \text{$M$is monotone}\}$ is undecidable

That's a question from a home assignment by T. Zur: Say that a Turing machine $M$ is monotone if it halts on every input, and if the length of $w$ is greater than the length of $w'$ then $M$ performs ...
• 117
58 views

### Prove that DIFFERENTDFA, PDA {<M1, M2> | Where M1 is a DFA and M2 is a PDA where L(M1)≠L(M2)} is undecidable

I am absolutely stumped on this one. I am unsure of how to start with this one. I have thought to reducing the problem to Atm. Another thought I have had is to convert M1 to a PDA and use the ...
1 vote
50 views

• 113
1 vote
71 views

• 65
86 views

### Determine efficiently whether A can get infinitely larger than B by following a walk in the given graph

Person $A$ is chasing person $B$. Both people can only travel between $n$ vertices of a graph by running through one of $m$ one-way pipes labelled $1,2,\cdots, m$. For each pipe we know the starting ...
58 views

### Low-rank matrix completion is NP-hard

In looking into the problem of low-rank matrix completion / relaxations of the general problem to derive exact solutions, many papers cite that the original formulation is NP-hard but I cannot find a ...
34 views

### Decision problem

Prove the following theorem Let A and B be two languages on an alphabet Σ. If A ≤p B and B ∈ P, then A ∈ P. Could anyone be able to prove it?
21 views

### If a problem is Cook-reducible to a problem in NEXP, is it in NEXP too?

I get why that would be true for EXP but cannot extend the argument to NEXP.
1 vote
46 views

### Are all $\mathbf{P}$ languages $\mathbf{P}$-complete with respect to polynomial-time reduction?

Question: Is language $L \in \mathbf{P}$ also $\mathbf{P}$-complete with respect to polynomial-time reduction? My thoughts: Given a language $L \in \mathbf{P}$, we want to show that for any other ...
1 vote
47 views

### Proof of NP-hardness of the k-means clustering problem for $k\geqslant 3$

coming from the computing science side rather than from the data analysis one, I studied the k-means clustering problem for a short time and noticed that the NP-hardness of the problem for $k=2$ seems ...
42 views

### Is there a non PSPACE language s.t exponential padding of it is PSPACE?

I've had an exam in computational models a few days ago, and would like to check whether I made a mistake. The question goes like that: Is there a language $L \notin PSPACE$ over the alphabet {0,1} ...
• 21
1 vote
73 views

### Why NP-Complete reduction is not reversible?

I have read the question asked here Is polynomial reduction reversible and the logic actually makes sense to me. In other words, if A is polynomially reducible to B, it means that A <= B in terms ...
• 65
1 vote
470 views

### Show that a subproblem of Sparse Subgraph is $\mathcal {NP}$-Complete

I want to show that a subproblem of the known, $\mathcal {NP}$-Complete, Sparse Subgraph problem is also $\mathcal {NP}$-Complete. Sparse Subgraph problem: Input: Undirected graph $G(V,E)$, two ...
• 133