Questions tagged [p-hardness]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
0 answers

Barriers and ETH, or its variants

ETH (Exponential Time Hypothesis) or its variants SETH(Strong ETH), NSETH(Non Deterministic SETH) haven't been resolved as yet. But resolution to any of the above hypotheses could lead to interesting ...
user3483902's user avatar
  • 1,181
1 vote
0 answers

proof that 2-SAT is P-hard [closed]

i'm doing university work about the 2-sat problem and it is asked why 2-sat is p-hard. We discussed that 3-sat is np-hard and proved this by reduction from cnf-sat to 3cnf-sat. for my work the ...
hellothere's user avatar
6 votes
1 answer

What is the complexity of HORN-2CNF entailment?

I know the entailment of a propositional variable in a HORN-3CNF formula is $P$-complete. I can't find any publication in which it has been shown the complexity of the same problem for HORN-2CNF ...
Abel Freid's user avatar
1 vote
1 answer

Recursively presenting or even enumerating all P-hard languages

A class of languages $C$ is recursively presentable if there is an effective enumeration of Turing machines $\mathcal{M}_1,\mathcal{M}_2,\ldots$ such that $C=\{L(\mathcal{M}_i)\mid i=1,2,\ldots\}$. ...
mak's user avatar
  • 504
14 votes
4 answers

P-complete problems on trees

This question is related to one of my previous questions, NP-hard problems on trees. I am looking for problems that are P-complete on trees.
Shiva Kintali's user avatar
11 votes
1 answer

Density of P-complete languages

Suppose $L$ is a Boolean language, of finite strings over $\{0,1\}$. Let $L_n$ be the number of strings in $L$ with length $n$. For a function $d(n)$ from the positive integers to the positive real ...
András Salamon's user avatar
42 votes
2 answers

Are the problems PRIMES, FACTORING known to be P-hard?

Let PRIMES (a.k.a. primality testing) be the problem: Given a natural number $n$, is $n$ a prime number? Let FACTORING be the problem: Given natural numbers $n$, $m$ with $1 \leq m \leq n$, ...
k m's user avatar
  • 421