Structural complexity of rational interactive proofs

DOI10.1007/978-3-031-36978-0_19MaRDI QIDQ6149048zbMATH OpenOpenAlexFDO

Authors Daniil Musatov, Georgii Potapov

Publication date 12 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2305.04563

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx)

Abstract: This is the full version of a paper submitted to the Computability in Europe (CiE 2023) conference, with all proofs omitted there. In 2012 P. D. Azar and S. Micali introduced a new model of interactive proofs, called "Rational Interactive Proofs". In this model the prover is neither honest nor malicious, but rational in terms of maximizing his expected reward. In this article we explore the connection of this area with classic complexity results. In the first part of this article we revise the ties between the counting hierarchy and the hierarchy of constant-round rational proofs. We prove that a polynomial-time machine with oracle access to DRMA[k] decides exactly languages in DRMA[k], a coincidence unknown for levels of the counting hierarchy. In the second part we study communication complexity of single-round rational proofs. We show that the class defined by logarithmic-communication single-round rational proofs coincides with PP. We also show that single-round rational protocols that treat problems in Parity-P as black-box samplers of a random variable require at least a linear number of bits of communication.

Recommendations

• Rational proofs
• Rational proofs with multiple provers
• Rational sumchecks
• Efficient rational proofs for space bounded computations
• Sequentially composable rational proofs

Cites work

• scientific article; zbMATH DE number 7525466 (Why is no real title available?)
• Algebraic methods for interactive proof systems
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Efficient rational proofs for space bounded computations
• Efficient rational proofs with strong utility-gap guarantees
• IP = SPACE
• Non-deterministic exponential time has two-prover interactive protocols
• On the power of multi-prover interactive protocols
• PP is as Hard as the Polynomial-Time Hierarchy
• PP is closed under truth-table reductions
• Rational arguments: single round delegation with sublinear verification
• Rational proofs
• Rational proofs with multiple provers
• Sequentially composable rational proofs
• The Knowledge Complexity of Interactive Proof Systems
• The complexity of combinatorial problems with succinct input representation

This page was built for publication: Structural complexity of rational interactive proofs

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