Linked Questions

1
vote
0answers
75 views

Undecidability of an existential theory

$F[u, u^{-1}]$ is a ring that contains the polynomials in $u$ and $u^{-1}$ with coefficients in the field $F$. Some theorems (from https://math.stackexchange.com/questions/1382120/ft-has-undecidable-...
0
votes
0answers
63 views

Is $k$-Clique NP-hard? [duplicate]

On my lecture note it was written that "Finding a clique of size $k$ in a graph is NP". Later in an example for reduction the following was written: "Assume we know how to answer "Is there a clique ...
1
vote
0answers
51 views

Finite State Machine trasition possibilities

Im studying finite state machines, in particular the deterministic and the non-deterministic versions. What i have not understood is : why in a non-deterministic state machine it's allowed that ...
0
votes
0answers
44 views

How can I determine whether a problem is NP-Hard [duplicate]

So I have a problem, I'm highly confident that it's NP-Hard, though I'm not really sure how I can convince my self this is the case? Suppose I have different groups of people m in a list M= {m1, m2} ...
0
votes
0answers
37 views

Prove the language L of all palindromes over {0,1} is in NP

Wouldn't this language be in P, since it is a context free language. And every context free language is a member of P? Or would it be otherwise?
0
votes
0answers
20 views

Does having a similar constraint while reducing a problem to similar problem to prove np hard means they are same?

I have been trying to find the computational complexity of my optimization problem and found that it is Np-Hard. To prove it to Np-Hard, I try reducing it Nurse Scheduling Problem. I am quite confused ...

15 30 50 per page
1
5 6 7 8
9