English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consolidate two widely believed conjectures about tautologies -- nooptimal proof system exists, and most require superpolynomial size proofs inany system -- into a $p$-isomorphism-invariant condition satisfied by allpaddable $\textbf{coNP}$-complete languages or none. The condition is: for anyTuring machine (TM) $M$ accepting the language, $\textbf{P}$-uniform inputfamilies requiring superpolynomial time by $M$ exist (equivalent to the firstconjecture) and appear with positive upper density in an enumeration of inputfamilies (implies the second). In that case, no such language is easy onaverage (in $\textbf{AvgP}$) for a distribution applying non-negligible weightto the hard families.  The hardness of proving tautologies and theorems is likely related. Motivatedby the fact that arithmetic sentences encoding "string $x$ is Kolmogorovrandom" are true but unprovable with positive density in a finitely axiomatizedtheory $\mathcal{T}$ (Calude and J{\"u}rgensen), we conjecture that anypropositional proof system requires superpolynomial size proofs for a dense setof $\textbf{P}$-uniform families of tautologies encoding "there is no$\mathcal{T}$ proof of size $\leq t$ showing that string $x$ is Kolmogorovrandom". This implies the above condition.  The conjecture suggests that there is no optimal proof system becauseundecidable theories help prove tautologies and do so more efficiently asaxioms are added, and that constructing hard tautologies seems difficultbecause it is impossible to construct Kolmogorov random strings. Similarconjectures that computational blind spots are manifestations ofnoncomputability would resolve other open problems.

Average-Case Hardness of Proving Tautologies and Theorems