Questions tagged [p-hardness]
The p-hardness tag has no usage guidance.
7
questions
3
votes
0
answers
190
views
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 ...
- 1,181
1
vote
0
answers
341
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
295
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 ...
- 133
1
vote
1
answer
176
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\}$. ...
- 504
14
votes
4
answers
736
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.
- 10.6k
11
votes
1
answer
313
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 ...
- 18.9k
42
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$, ...
- 421