Hacker News
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
almostgotcaught
on Jan 9, 2025
|
parent
|
context
|
favorite
| on:
SAT Solver Etudes I
> However, in practice variable-fixing can and often does give an _expected time_ speed-up
Proof? Because as far as I know literally none of RP, BPP, ZPP relationships to NP are known.
madars
on Jan 9, 2025
[–]
Indeed no proof. By "in practice" I meant "on instances encountered in real-world applications."
almostgotcaught
on Jan 9, 2025
|
parent
[–]
then instead of _expected time_ you should say _hope-for time_ because _expected time_, in this context, is already firmly defined.
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search:
Proof? Because as far as I know literally none of RP, BPP, ZPP relationships to NP are known.