Note on constrained long choice with multiple beginning elements

DOI10.1007/S00224-024-10209-4MaRDI QIDQ6661767zbMATH OpenFDO

Authors Takashi Ishizuka

Publication date 13 January 2025

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00224-024-10209-4

zbMATH Keywords

computational complexityPLCPLSTFNPTuring closure

Mathematics Subject Classification ID

Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Extremal combinatorics, iterated pigeonhole arguments and generalizations of PPP
• On Search Problems in Complexity Theory and in Logic (Abstract)
• Propositional proofs and reductions between NP search problems
• A note on the complexity of local search problems

Cites work

• Consensus halving is PPA-complete
• Extremal combinatorics, iterated pigeonhole arguments and generalizations of PPP
• Further collapses in TFNP
• How easy is local search?
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• Integer factoring and modular square roots
• On Search Complexity of Discrete Logarithm
• On the complexity of finding falsifying assignments for Herbrand disjunctions
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Settling the complexity of computing two-player Nash equilibria
• The frontier of intractability for EFX with two agents
• Towards a unified complexity theory of total functions
• Unique end of potential line

Cited in

(1)

• Extremal combinatorics, iterated pigeonhole arguments and generalizations of PPP

This page was built for publication: Note on constrained long choice with multiple beginning elements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6661767)