Questions tagged [p-hardness]
The p-hardness tag has no usage guidance.
6
questions
1
vote
0
answers
132
views
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 ...
- 11
6
votes
1
answer
282
views
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 ...
- 776
1
vote
1
answer
128
views
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\}$. ...
- 464
14
votes
4
answers
726
views
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.
CommunityBot
- 1
41
votes
2
answers
2k
views
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$, ...
- 527
11
votes
1
answer
298
views
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 ...
CommunityBot
- 1