8 votes
Accepted

What is the complexity of HORN-2CNF entailment?

I don't know any publication where this is stated, but it is an $NLOGSPACE$-complete. For the lower bound one can give a reduction from the reachability problem, which is the problem of determining ...
Reijo Jaakkola's user avatar
7 votes
Accepted

Complexity of reachability in directed rooted forests

The problem is L-complete. It’s easier to think about it when the edges are written backwards. That is, I will consider the problem formulated as follows: given a directed acyclic graph such that ...
Emil Jeřábek's user avatar
7 votes
Accepted

Why is the "general notion of a reduction [...] inherent to the notion of self-reducibility"?

I think you may be misunderstanding the sentence "Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent." This is not about reductions being inherent to self-reducibility (...
Sasho Nikolov's user avatar
3 votes

Is there an algorithm which gets incrementally "smarter" as it runs?

Let's assume you're working on a toy programming language Flarp late at night and someone whispers in your ear a great deal of its particular Chaitin's Omega and you're clever enough to realize what ...
jberryman's user avatar
  • 131
2 votes

What are the general direction and target question in the field of quantum error correction?

One big open question is the existence of "good" quantum LDPC codes. These are stabilizer quantum error correcting codes with constant check weight, constant rate and linear distance. Most ...
smapers's user avatar
  • 849
2 votes

What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

Let $n$ be the total number of elements in all sets in $F$, basically your input size. Maintain a priority queue of the remaining sets, prioritized by cost / number of uncovered elements. Every time ...
David Eppstein's user avatar
2 votes
Accepted

A conceptual question regarding hardness proofs by reduction

In your question, did you just restrict the input of two problems? If yes, this is wrong. Consider problem A which is NP-complete. You can trivially reduce A to itself! So, do you think a restriction ...
Mohemnist's user avatar
  • 230
2 votes

Is there an algorithm which gets incrementally "smarter" as it runs?

You can look at genetic programming, and perhaps neural networks, which are quite general algorithms that improve under usage. This is quite far from proving statements, but one can imagine that in a ...
Per Alexandersson's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible