Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
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
4 votes
Accepted

Recursively presenting or even enumerating all P-hard languages

After some further thought, partly triggered by writing a long question, it seems clear that the set of P-hard languages is not countable, and therefore not recursively presentable either. To see why,...
mak's user avatar
  • 504

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