Linked Questions

10 votes
2 answers
6k views

Mapping Reductions to Complement of A$_{TM}$

I have a general question about mapping reductions. I have seen several examples of reducing functions to $A_{TM}$ where $A_{TM} = \{\langle M, w \rangle : \text{ For } M \text{ is a turing machine ...
RageD's user avatar
  • 203
2 votes
2 answers
8k views

Is the language TMs that accept finite languages Turing-recognizable?

I know that $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not decidable (by Rice's theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable? What I ...
advocateofnone's user avatar
8 votes
3 answers
689 views

What is the name of this logistic variant of TSP?

I have a logistic problem that can be seen as a variant of $\text{TSP}$. It is so natural, I'm sure it has been studied in Operations research or something similar. Here's one way of looking at the ...
Juho's user avatar
  • 22.5k
1 vote
1 answer
12k views

Proving a language is not Turing-recognizable by reduction from $D = \{\langle M\rangle \mid M \text{ rejects input }\langle M\rangle\}$

I'm having a really hard time understanding some of these concepts. I've read them over from several different sources and still can't reach the a-ha moment. I need to prove a language $L$ is not ...
Tanner's user avatar
  • 11
7 votes
2 answers
527 views

primitive recursive functional equivalence

Given two primitive recursive functions is it decidable whether or not they are the same function? For example lets take sorting algorithms A, and B which are primitive recursive. While there are many ...
44701's user avatar
  • 459
1 vote
2 answers
4k 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 ...
proX's user avatar
  • 29
3 votes
2 answers
2k views

Need Help Reducing Subset Sum to Show a Problem is NP-Complete

I want to show that the following problem is NP-Complete: For a set of vectors $v_1,\ldots,v_n \in \mathbb{N}^d$ and an integer $k$, does there exist a subset $S \subseteq \{v_1,\ldots,v_n\}$, such ...
Newb's user avatar
  • 314
5 votes
1 answer
3k views

Showing a problem is NP complete? Reducing CLIQUE to KITE.

I've got an exam next week all about this sort of thing. Ie: Find polynomial certifier for a problem, give a polynomial reduction, prove problem X reduces to Y and etc. The problem is, there doesn't ...
Jay's user avatar
  • 53
2 votes
3 answers
2k views

Prove that finding largest subset of undirected graph that is almost independent is NP-hard

A subset $S$ of vertices in an undirected graph $G$ is called almost independent if at most 100 edges in $G$ have both endpoints in $S$. Prove that finding the size of the largest almost-independent ...
AndroidFish's user avatar
2 votes
3 answers
3k views

Can the edges of a graph be assigned directions such that all nodes in a given subset have in- or outdegree 0, and every other node indegree > 0?

In a directed graph, the indegree of a node is the number of incoming edges and the outdegree is the number of outgoing edges. Show that the following problem is NP-complete. Given an undirected graph ...
kiran's user avatar
  • 37
3 votes
3 answers
358 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 ...
qalis's user avatar
  • 169
1 vote
2 answers
949 views

How to show the function is not Turing computable?

Having the function: $$f(y) = \begin{cases} \ 1 &\text{if }\forall n \Phi_y(n)=n\lor \Phi_y(n) \!\uparrow\\ \ 0 &\text{otherwise.} \end{cases}$$ By the rule of thumb it ...
TechCrap's user avatar
  • 145
3 votes
2 answers
2k views

Negative simple path NP-Complete

Given a graph $G=(V,E)$, and positive and negative edge weights, negative path problem asks if there is a simple path with negative total weight from $s$ to $t$ where $s,t \in V$ My approach was to ...
Kaan Yolsever's user avatar
3 votes
1 answer
2k views

Is regularity of the language accepted by a given Turing machine a semi-decidable property?

Given is the definition of a general problem: $\{ \langle M, S\rangle \mid M \text{ is a } TM, L_M \in S\}$. In words: Given a TM M, does M decide a language that is an element of the given set of ...
Ad Fundum's user avatar
  • 229
1 vote
1 answer
2k views

Proving a language is neither Recursively Enumerable nor co-Recursively Enumerable

$$L = \{ \langle M \rangle \mid \text{\(M\) is a Turing Machine and \(|L(M)| = 1\)} \}$$ I have to prove that this is not R.E. and not co-R.E. I know how to approach these kind of problems. For $\...
parsimony's user avatar

15 30 50 per page