Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

4,750 questions
Filter by
Sorted by
Tagged with
88 views

NP-hardness proof of an optimization problem with real values and rational input in the decision problem

I'm studying complexity theory and I have the below question regarding $NP$-hardness proofs of optimization problems with real values. Any reference is much appreciated. For the question, take the ...
53 views

How to encode a Universal Turing machine to an Integer $\in\mathbb{N}^+$?

The proof of Hierarchy Theorems (including space hierarchy theorem, deterministic time hierarchy theorem, nondeterministic time hierarchy theorem) depend on constructing a Universal Turing machine ...
17 views

Prove that if $k$ was the $(i+1)$st key to be inserted into the hash table, then $E[probes(k)]=\frac{1}{1-\frac{i}{m}}$

Theorem: Inserting an element into an open-address hash table with load factor α requires at most $1/(1 − α)$ probes on average, assuming uniform hashing. By following unsuccessful search strategy, we ...
Theorem: Given an open-address hash table with load factor $α = n/m < 1$, the expected number of probes in an unsuccessful search is at most $1/(1−α)$, assuming uniform hashing. Let us define the ...