I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How should I approach a problem that asks me to prove a problem is NPC?

Is it not possible to view FACTOR as a special case of KNAPSACK? When I see the knapsack problem, or subset sum for that matter, I see a factoring problem. If the language for factoring is: FACTOR = {(N,r) there is a g, 1 < g < r, such that f(g) = 0 ∑xi = g, xi⊆ {1, . . . , n}, f(g) = ...

In many text books NP problems are defined as: Set of all decision problems solvable by non deterministic algorithms in polynomial time I couldn't understand the part "solvable by non deterministic algorithms". Anyone please explain that

I need to cover these topics in Role Mining. If anyone knows good site which well summarizes the topics and concepts are well explained please help out. Basic role mining problem • Delta-approx RMP • Min-noise RMP • Nature of the RMP problems • Mapping RMP to database tiling problem • Minimum ti...

Some users are not familiar with the LaTeX notations, which is perfectly fine, but it would be better if we could refer them to some FAQ/help page that explain the basic commands, in a similar way to the markdown edit-help. I suggest to add to the editing help page a short summary of basic Latex...

Imagine a completely sequential program $P$ written as a sequence of instructions $(i_1, i_2, ..., i_n)$. Define a class of relations over the set $I$ of all possible instructions as follows: $S_P$, where $i S_P j$ if and only if $i$ must be executed before $j$ in order to guarantee an executio...

Given a set of elements $$\Sigma = \{\sigma_1, \sigma_2, ..., \sigma_n\}$$ and a set of triplets $$S = \{(\sigma_i, \sigma_j, \sigma_k) | \sigma_i, \sigma_j, \sigma_k \in \Sigma, i \neq j, j \neq k, i \neq k\}$$ find an algorithm which either constructs an ordering $\rho_S = (\sigma_{m_1}, \sigma...