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-...
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 ...
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 ...
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} ...