Problem Detail: Quantified Boolean formulae are the prime examples of problems that are hard for the polynomial hierarchy, i.e., for the $Pi$ and $Sigma$ versions of it. However, there is also the $Delta$ version, defined as $Delta_{i+1}^{rm P} := {rm P}^{Sigma_i^{rm Read More …
Author: ignougroup
[Solved]: Algorithm analysis in the presence of undefined functions
Problem Detail: I wonder how we can perform algorithm analysis when in an algorithm we have calls of functions whose definition we do not know, e.g. functions delivered by external libraries. Asked By : marekszpak Answered By : David Richerby There are two Read More …
[Solved]: Is summing over all possible $k$-combinations NP-hard?
Problem Detail: Say we have a set of numbers $A={a_1, a_2, dots, a_n}$, and we wish to sum over all possible combinations of $k$ terms to compute $$ sum_{substack{C subseteq {1,2,dots,n} |C|=k}} prod_{c in C} a_c $$ Naively this requires $O(kbinom{n}{k})$ Read More …
[Solved]: A variant of the busy beaver function
Problem Detail: Reading this question “Natural RE undecidable problems but not Turing-complete” the following language came to my mind: If $Sigma(cdot)$ is the busy beaver function (maximum attainable score among all halting 2-symbol n-state Turing machines of the above-described type, when Read More …
[Solved]: Are randomized algorithms constructive?
Problem Detail: From , the proofs by the probabilistic method are often said to be non-constructive. However, a proof by probabilistic method indeed designs a randomized algorithm and uses it for proving existence. Quoted from p103 of Randomized Algorithms By Rajeev Read More …
[Solved]: Inapproximability result implies apx-hardness?
Problem Detail: If an optimization problem is known to be inapproximable up to some precision, does this automatically imply that the problem is apx-hard? Asked By : mat Answered By : Yuval Filmus If P$=$NP then there is a polytime algorithm for any Read More …
[Solved]: Is there a simple example of sets such that $A leq_T B$ but not $A leq_m B$?
Problem Detail: I wonder if there is a simple example of sets $A$ and $B$ such that $A$ is Turing-reductible to $B$ but not many-to-one reductible to $B$. Asked By : pintoch Answered By : Martin Jonáš For example sets $H = {x Read More …
[Solved]: Can a Turing machine decide if a LOOP program stops for the integer input 0
Problem Detail: This is a question I found in a practice exam while I am preparing for my mid term exam. The answer needs justification, either a pseudo code or a logical explanation why not. What puzzled me about that question Read More …
[Solved]: When testing n items, how to cover all t-subsets by as few s-subsets as possible?
Problem Detail: This problem arose from software testing. The problem is a bit difficult to explain. I will first give an example, then try to generalize the problem. There are 10 items to be tested, say A to J, and a Read More …
[Solved]: Complement of HAMPATH
Problem Detail: Is the complement of the Hamiltonian Path problem known to be in $mathsf{NP}$? I could not find explanations saying that it is, but then neither were there any claims saying that it is not in $mathsf{NP}$. Asked By : pnp Read More …
