Recent zbMATH articles in MSC 68Q15https://zbmath.org/atom/cc/68Q152024-08-28T19:40:24.813883ZWerkzeugP-optimal proof systems for each NP-set but no complete disjoint NP-pairs relative to an oraclehttps://zbmath.org/1539.031862024-08-28T19:40:24.813883Z"Dose, Titus"https://zbmath.org/authors/?q=ai:dose.titusSummary: \textit{P. Pudlák} [Bull. Symb. Log. 23, No. 4, 405--441 (2017; Zbl 1423.03245)] lists several major conjectures from the field of proof complexity and asks for oracles that separate corresponding relativized conjectures. Among these conjectures are:\begin{itemize}\item[--] \(\mathrm{DisjNP}\): The class of all disjoint \(\mathrm{NP}\)-pairs has no many-one complete elements.\item[--] \(\mathrm{SAT}\): \(\mathrm{NP}\) contains no many-one complete sets that have \(\mathrm{P}\)-optimal proof systems.\item[--] \(\mathrm{UP}\): \(\mathrm{UP}\) has no many-one complete problems.\item[--] \(\mathrm{NP}\cap\mathrm{coNP}\): \(\mathrm{NP}\cap\mathrm{coNP}\) has no many-one complete problems.\end{itemize} As one answer to this question, we construct an oracle relative to which \(\mathrm{DisjNP}\), \(\neg\mathrm{SAT}\), \(\mathrm{UP}\), and \(\mathrm{NP}\cap\mathrm{coNP}\) hold, i.e., there is no relativizable proof for the implication \(\mathrm{DisjNP}\wedge\mathrm{UP}\wedge\mathrm{NP}\cap\mathrm{coNP}\Rightarrow\mathrm{SAT}\). In particular, regarding the conjectures by Pudlák [loc. cit.] this extends a result by \textit{E. Khaniki} [J. Symb. Log. 87, No. 3, 912--937 (2022; Zbl 1531.03097)]. Since Khaniki [loc. cit.] constructs an oracle showing that the implication \(\mathrm{SAT}\Rightarrow\mathrm{DisjNP}\) has no relativizable proof, we obtain that the conjectures \(\mathrm{DisjNP}\) and \(\mathrm{SAT}\) are independent in relativized worlds, i.e., none of the implications \(\mathrm{DisjNP}\Rightarrow\mathrm{SAT}\) and \(\mathrm{SAT}\Rightarrow\mathrm{DisjNP}\) can be proven relativizably.
For the entire collection see [Zbl 1423.68036].Complexity of natural numbershttps://zbmath.org/1539.110232024-08-28T19:40:24.813883Z"Arias de Reyna, Juan"https://zbmath.org/authors/?q=ai:arias-de-reyna-martinez.juanSummary: This is the English version of the author's paper [Complejidad de los números naturales, Gac. R. Soc. Mat. Esp. 3, No. 2, 230--250 (2000; Zbl 1358.68107). The complexity \(\|n\|\) of a natural number \(n\) is the least number of \(1\)'s needed to write an expression for \(n\) using only the addition \(+\), the product \(\ast\), the unit 1, and parentheses \((\,)\). We study its main properties and end up formulating a set of conjectures. These conjectures are now mainly resolved by the work of Harry Altman. We include an appendix explaining these later results.