We consider the efects of allowing a finite state verifier in an interactive proof system to use a bounded number of private coins, in addition to “public” coins whose outcomes are visible to the prover. Although swapping between private and public-coin machines does not change the class of verifiable languages when the verifiers are given reasonably large time and space bounds, this distinction has well known efects for the capabilities of constant space verifiers. We show that a constant private-coin “budget” (independent of the length of the input) increases the power of public-coin interactive proofs with finite state verifiers considerably, and provide a new characterization of the complexity class P as the set of languages that are verifiable by such machines with arbitrarily small error in expected polynomial time.
In addition to providing a new perspective on the age-old concept of “proof” and ofering
possibilities for weak clients to check the correctness of dificult computations that they delegate
to powerful servers, interactive proof systems also play an important role in the characterization
of computational complexity classes [
Several specializations of the basic model described above have been studied until now. One
parameter is whether the prover can “see” the outcomes of the random choices made by the
verifier or not. A “private-coin” system hides the results of the verifier’s coin flips from the
prover, and the verifier only sends information that it deems necessary through a communication
channel. “Public-coin” systems, on the other hand, hide nothing from the prover, who can
be assumed to observe the coin flips and deduce the resulting changes to the configuration
of the verifier as they unfold. It is known [
In this paper, we study the capabilities of constant-space verifiers (essentially, two-way probabilistic finite automata) which are allowed to hide some, but not necessarily all, of their coin flips from the prover. We show that allowing these machines to use even only a constant number1 of private coins enlarges the class of verified languages considerably. We adapt several previous results from the literature to this framework and present a new characterization of the complexity class P as the set of languages that can be verified by such machines in polynomial time with arbitrarily small error.
We start by providing definitions of interactive proof systems and related language classes that
are general enough to cover finite state verifiers with both private and public coins, as well as
the more widely studied versions with greater memory bounds [
A verifier in an interactive proof system (IPS) is a 6-tuple (, Σ , Φ , Γ , , 0), where 1. is the finite set of states, such that = pri ∪ pub ∪ { acc, rej } where • pri is the set of states that flip private coins, • pub is the set of states that flip public coins, pri ⊆ pub, and • acc, rej ∈/ pri ∪ pub are the accept and reject states, respectively,
3. Φ is the work tape alphabet, which is guaranteed to include the special blank symbol, ,
∈ Γ ,
6. 0 is the initial state, 0 ∈ .
The computation of a verifier is initialized with ▷◁ written on its read-only input tape, where ∈ Σ * is the input string, and ▷, ◁ ∈/ Σ are the left and right end-markers, respectively. The input head of the verifier is initially on the left end -marker. The read-write work tape is initially filled with blank symbols, with the work tape head positioned at the beginning of the tape. Apart from these two tapes, the verifier also has access to a communication cell, which is a single-cell tape that is initially blank.
Let Σ ◁▷ = Σ ∪ { ▷, ◁ }. Let ∆ = { − 1, 0, +1 } be the set of possible head movements, where − 1 means “move left”, 0 means “stay put”, and +1 means “move right”. 1That is, the number of such private coin flips is fixed, regardless of the length of the input.
The computation of a verifier evolves by its transition function , which is constructed in two parts as follows: For ∈ pri (which implies ∈ pub), (, , , , pri, pub) = (′, ′, ′, , ) dictates that if the machine is originally in state , scanning ∈ Σ ◁▷ in the input tape, ∈ Φ in the work tape, and ∈ Γ in the communication cell, and has obtained the “private” random bit pri ∈ { 0, 1 } and the “public” random bit pub ∈ { 0, 1 } as the result of two independent fair coin flips, then it will switch to state ′ ∈ , write ′ ∈ Φ to the work tape, overwrite the communication cell with ′, and move the input and work tape heads in the directions , ∈ ∆ respectively. For ∈ pub ∖ pri, (, , , , pub) = (′, ′, ′, , ) dictates a similar transition in which the outcome of only a single public coin is used.
The verifier is paired with another entity, the prover, whose aim is to convince the verifier to accept (or to prevent it from rejecting) its input string. At every step of the verifier’s execution, the outcome of the public coin flip is automatically communicated to the prover. The prover can be modeled as a function that determines the symbol ∈ Γ which will be written in the communication cell in between the transitions of the verifier based on the input string, the public coin outcomes, and the sequence of symbols written by the verifier to the communication cell up to that point. Note that the prover does not “see” (and, in the general case, cannot precisely deduce) the configuration of a verifier which uses private coins.
A verifier halts with acceptance (rejection) when it executes a transition entering acc (rej). Any transition that moves the input head beyond an end-marker delimiting the string written on the read-only input tape leads to a rejection, unless that last move enters acc. Note that the verifier may never halt, in which case it is said to be looping.
We say a verifier in an IPS verifies a language with error = max(+, − ) if there exist numbers +, − < 1/3 where • for all input strings ∈ , there exists a prover such that halts by accepting with probability at least 1 − + when started on and interacting with , and, • for all input strings ∈/ and for all provers * , halts by rejecting with probability at least 1 − − when started on and interacting with * .
The terms + and − bound the two possible types of error corresponding to failing to accept and reject, respectively. Intuitively, this definition requires (in order for it to keep its error low) to be reasonable enough to accept legitimate arguments that prove that the input is a member of the language in question, yet skeptical enough to reject spurious claims of membership when the input is not in the language, both with high probability, even when it is interacting with the most cunning of all provers.
In some of our proofs in Section 3, we will be considering verifiers with multiple input tape heads that the machine can move independently of one another. This type of verifier can be modeled easily by modifying the tuples in the transition function definitions above to accommodate more scanned input symbols and input head directions. Sections 2.2 and 2.3 provide more information on automata with multiple input heads and their relationships with the standard Turing machine model.
We will be using the notation IP(resource1, resource2, . . . , resource) to denote the class of languages that can be verified with arbitrarily small (but possibly positive) errors by machines that operate within the resource bounds indicated in the parentheses. These may represent budgets for runtime, working memory usage, and number of public and private random bits, given as a function of the length of the input string, in asymptotic terms. We reserve the symbol to denote the length of the input string. The terms con, log, linear, and poly will be used to represent the well-known types of functions to be considered as resource bounds, with “con” standing for constant functions of the input length, the others being self evident, to form arguments like “poly-time” or “log-space”. The absence of a specification for a given type of resource (e.g., private coins) shall indicate that that type of resource is simply unavailable to the verifiers of that class. 2
By default, a given resource budget should be understood as a worst case bound, indicating that it is impossible for the verifier to exceed those bounds. Some of the interactive protocols to be discussed have the property that the verifier has a probability of being fooled to run forever by a malicious prover trying to prevent it from rejecting the input. The designer of the protocol can reduce to any desired small positive value. The denotation “* ” will be used to mark that the indicated amount corresponds to such a machine’s expected consumption of a specific resource with the remaining (high) probability 1 − . For instance, “poly* -time” will indicate that the verifier’s expected runtime is polynomially bounded with probability almost, but possibly not exactly, 1.
Our work makes use of an interesting relationship [
A -head nondeterministic finite automaton (2nfa()) is a nondeterministic finite-state machine with read-only heads that move on an input string flanked by two end-marker symbols. Each head can be made to stay put or move to an adjacent tape cell in each computational step. Formally, a 2nfa() is a 4-tuple (, Σ , , 0), where 1. is the finite set of internal states, which includes the two halting states acc and rej, 2. Σ is the finite input alphabet, 3. : × Σ ◁▷ → ︀( × ∆ )︀ is the transition function describing the sets of alternative moves the machine may perform at each execution step, where each move is associated with a state to enter and whether or not to move each head, given the machine’s current state and the list of symbols that are currently being scanned by the input heads, and Σ ◁▷ and ∆ are as defined previously in Section 2.1, and 4. 0 ∈ is the initial state.
Given an input string ∈ Σ * , a 2nfa() = (, Σ , , 0) begins execution from the state 0, with ▷◁ written on its tape, and all of its heads on the left end-marker. At each step, 2Verifiers that use only some private coins and no public coins can be described in the framework given above by simply specifying their transition functions to be insensitive to the value of the public random bit argument, i.e., (, , , , pri, 0) = (, , , , pri, 1) and (, , , , 0) = (, , , , 1) for all values of , , , , and pri. nondeterministically updates its state and head positions according to the choices dictated by its transition function. Computation halts if one of the states acc or rej has been reached, or a head has moved beyond either end-marker.
is said to accept if there exists a sequence of nondeterministic choices where it reaches the state acc, given as the input. is said to reject if every sequence of choices either reaches rej, ends with a transition whose associated set of choices is ∅, or by a head moving beyond an end-marker without a final state being entered. might also loop on the input , neither accepting nor rejecting it.
The language recognized by is the set of strings that it accepts.
Let ℒ(2nfa(* )) denote the set of languages that have a 2nfa() recognizer (for some > 0), and ℒ(2nfa(* ), linear-time) denote the set of languages that have a 2nfa() recognizer running in linear time.
Our main result will be making use of a technique introduced by Say and Yakaryılmaz [
The equivalence of multiple input heads and logarithmic amounts of memory was discovered
by Hartmanis [
Theorem 1. Any language recognized by a Turing machine that uses at most ⌈log ⌉ space with a work tape alphabet of size at most 2 (for some integer constant > 0) and in () time can also be recognized by a ( + 5)-head finite automaton in () · (1 + + 2 + 3) time. Proof idea. Assume, for the sake of simplicity, that is a power of 2. A string over the alphabet { 0, 1 } in a work tape of length log can be seen as the digits of a number between 0 and − 1, inclusive, represented in binary. The index of a head on the input tape can similarly range between 0 (when on ▷) and + 1 (when on ◁). This correspondence enables a multihead finite automaton to store the same information there is on a log symbol string over an alphabet of size 2 (which can be viewed as the binary digits of numbers stacked on top of each other), encoded at the indices of input heads.
There is a way for a multihead finite automaton to retrieve a single binary digit of a head’s index and also to change it. Four spare input heads are introduced and used to accomplish these functions, with one of them mimicking the position of the simulated work tape head, and the other three helping with the index manipulations for decoding, changing, and then re-encoding. One last input head is the input head of the multihead finite automaton.
Using this method, a multihead finite automaton can simulate a ⌈log ⌉-space Turing machine directly.
A logarithmic-space Turing machine can “clock” its own execution to satisfy any desired polynomial time bound by counting up till that bound in the logarithmic space available. The constant-space machines we construct in Section 3 will employ a diferent technique using randomness, which is illustrated in the following lemma, to obtain the same bound on expected runtime.
Lemma 2. For any constant > 0, integer-valued function () ∈ O (︀ )︀ , and desired “error” bound premature > 0, there exists a probabilistic finite automaton with an expected runtime in O (︀ +1)︀ , such that the probability that this machine halts in fewer than () time-steps is premature.
Proof idea. Assume, for the sake of simplicity, that is an integer. We program a probabilistic ifnite state automaton to make random walks with its input head, each starting from the first symbol on the input and ending at either one of the end-markers. If all the walks have ended on the right end-marker, the machine halts. Otherwise, the process is repeated. The analysis shows that such a machine has all the necessary characteristics in its runtime.
Let us consider the language of palindromes, pal = {︀ ∈ { 0, 1 }* ⃒⃒ = }︀ , where is the reverse any string . Trivially, pal ∈ ℒ(2nfa(* ), linear-time).
We recall the following facts about the power of finite state verifiers at the two extreme ends
of the “public vs. private” spectrum, which shows us that even a finite amount of private coins
gives verifiers an edge that no amount of public coins can compensate:
Fact 3. pal ∈/ IP(con-space, ∞-public-coins, ∞-time) [
Fact 4. ℒ(2nfa(* ), linear-time) ⊆ IP(con-space, con-private-coins, linear* -time) [7].3
Let us now examine the efects of allowing finite state verifiers to hide a constant number of their coin flips from the prover. This turns out to provide a new characterization of the complexity class P, corresponding to the collection of languages decidable by deterministic Turing machines in polynomial time and space.
Theorem 5.
IP(con-space, con-private-coins, poly* -public-coins, poly* -time) = P.
3Recall from the definition of our IP complexity class notation in Section 2 that the verifier’s runtime can be infinite
with probability at most , and its expected runtime is bounded as indicated with the remaining large probability.
Proof. It is known [
IP(log-space, poly-public-coins, poly-time) = P.
Lemma 6.
IP(log-space, poly-public-coins, poly-time) ⊆ More specifically, for any > 1,
IP(log-space, O(︀ )︀ -public-coins, O(︀ )︀ -time) ⊆
IP(con-space, con-private-coins, poly* -public-coins, poly* -time).
IP(con-space, con-private-coins, O(︀ +2)︀ * -public-coins, O(︀ +2)︀ * -time).
Proof. For some > 1, let 1 be a public-coin verifier that uses O (log ) space and O (︀ )︀ time
to verify the language with error 1 > 0. We will assume that the work tape of 1 is exactly
⌈log ⌉ cells long, but with a “multi-track” alphabet (e.g., as in [
In the following discussion, let any prover facing 1 be called 1. Since 1 cannot be fooled into accepting a non-member of with high probability no matter what prover it is facing, it is also immune against any such 1 that “knows” 1’s algorithm. Since all coins are public, such a 1 can be assumed to have complete knowledge about 1’s configuration at every step of their interaction. Therefore we will assume that 1 sends no further information through the communication cell without loss of generality.
Let us consider a constant-space, public-coin, -head verifier 2 that can verify by simply executing 1’s program, simulating 1’s logarithmic-length work tape by the means of Theorem 1. Since the simulation is direct and does not involve any additional use of randomness, 2 recognizes with the same probability of error 1. The only time overhead is caused by the simulation of the log-space memory, so, by Theorem 1, 2 will complete its execution in O (︀ +1)︀ time. Just like 1, 2 sends no information to its prover, say, 2, except the outcomes of its public coins.
We now describe 3, a constant-space, single-head verifier that uses a constant number of private coins (in addition to the public coins that it flips at every step) to verify . 3 performs the following verification for consecutive rounds:
First, 3 flips of its private coins. Thanks to this randomness, it picks the th head of 2 with some probability4 . 3 then engages in an interaction with its own prover, say, 3, to simulate the execution of 2, including 2’s interaction with 2 about the input string. In this process, 3 traces the selected head of 2 with its own single head, and relies on the messages of 3 to inform it about what the other heads of 2 would be reading at any step of the execution. 3 does not send any information (except, of course, the outcomes of its public coins) to 3. 3, on the other hand, is expected to transmit both 4We will discuss constraints on these values in the discussion below.
• what 2 would be transmitting to 2, and • its claims about the readings of all heads of 2 at every step of the simulated interaction. 3 verifies the part of these claims regarding the head it had chosen in private, and rejects if it sees any discrepancy. 3 sends a special symbol when it claims that the simulated interaction up to that point has ended with 2 reaching acceptance. If this is consistent with what 3 has been able to validate, and if this was not the th round, 3 proceeds to another round.
While is positive for all , the sum simulation = ∑︀ =1 is very small by design. With the remaining high probability timer = 1 − simulation, 3 passes this round operating as a probabilistic timer that has an expected runtime of O (︀ +2)︀ . This timer is also guaranteed to run longer than 2’s runtime with probability 1 − premature, for some positive premature that can be set to be arbitrarily close to 0, by the premise of Lemma 2. If 3 claims that 2 has accepted before the timer runs out, then 3 proceeds with another round of verification. Otherwise (if the timer runs out before 3 declares acceptance), 3 rejects.
3 accepts if it does not reject for rounds of verification. The total number of private coins used is .
The rest of the proof analyzes the error and runtime of 3.
Arbitrarily small verification error. For any input string that is a member of , 3 should tell 3 the truth about what 2 would read with its heads, and emit the messages 2 would send to 2 alongside those readings. Faced with such a truthful 3, 3 may erroneously reject at any given round, either due to the simulated 2 also rejecting,5 or due to a premature timeout of the probabilistic timer. The probability of that is simulation · 1 + timer · premature. For 3 to accept such an input string, it should go through consecutive rounds of verification without committing such errors. The probability that 3 will fail to accept a string in is therefore 3+ ≤ 1 − (︀ 1 − (︀ simulation · 1 + timer · premature)︀ .
For any input not in , 3 can accept only if 3 claims that 2 accepts in all rounds. Such a claim can either be true, since 2 can genuinely accept such a string with probability at most 1; or false, in which case 3 would be “lying”, i.e., providing false information that could be detected when compared against the actual readings of at least one of 2’s heads. Let min = min=1 . The probability of 3 failing to catch such a lie in any round is at most 1 − min. It follows that the probability that 3 accepts a string not in is −3 ≤
max(1, (1 − min)).
The last kind of verification error for 3 is getting tricked into running forever by an evil prover when given a non-member input string. The probabilistic timer function, when in play with probability timer, will keep 3 from running forever. The probability of 3 looping on the th round of its verification is at most max(1, (1 − min))− 1 · simulation (since it should pass 5Our definitions allow 2 to reject members of with some small probability. loop is at most the sum of those probabilities, i.e., the first − 1 rounds without rejecting in that case). The probability that 3 can be fooled to loop 3 ≤ simulation ·
∑︀=− 01 max(1, (1 − min)).
︁( 3 = max 3+, −3 , 3 loop)︁ .
Since all of these bounds can be lowered arbitrarily to any positive constant (by first increasing two), 3 can also be lowered to any desired positive constant. to constrain −3 , and then decreasing simulation > 0 and premature > 0 to constrain the other in O (︀ +2)︀ time with arbitrarily high probability.
Lemma 7.
Polynomial expected runtime with arbitrarily high probability. desired small value, 3 will be running for at most rounds with the remaining high probability. At each of those rounds, 3 will either complete 2’s simulation in O (︀ +1)︀ time or will operate as the probabilistic timer that has the expected runtime of O (︀ +2)︀ . Thus, it is expected to run 3 With loop set to a IP(con-space, con-private-coins, poly* -public-coins, poly* -time) ⊆ IP(log-space, poly-public-coins, poly-time).
More specifically, for any integer > 1,
IP(con-space, con-private-coins, O(︀ )︀ * -public-coins, O(︀ )︀ * -time) ⊆
IP(log-space, O(︀ +1)︀ -public-coins, O(︀ +1)︀ -time).
Proof. Let 1 be a (single-head) constant space verifier that uses at most private coins and an unlimited budget of public coins to verify a language , for some constant . The three types of errors that 1 may commit are that • it might reject a member of when communicating with an honest prover with some probability 1+, probability
l1oop. • it might be tricked to accept a non-member of with some probability −1 , • it might be tricked to run forever when the input is not a member of with some
1() ∈ O (︀ )︀ steps where > 1 is an integer. In the following, the prover that 1 interacts − loop), 1 is expected to terminate in 1 with will be named 1.
A constant space public-coin (2 + )-head verifier 2 can verify in polynomial time and with an error bound close to that of 1 as follows: 2 will run 2 parallel simulations (“sims”) of 1, where the th sim (for ∈ { 0, . . . , 2 − 1 }) assumes its private random bits as the bits of the binary representation of the number and uses the ( + 1)st head of 2. The prover that 2 interacts with, which we name 2, is supposed to mimic 1 by providing a 2-tuple containing the symbols that 1 would send to each at each step. At every step of its interaction, 2 performs the following three tasks: • It checks the communication symbol received from 2 to see if it is consistent with the simulated interaction that took place up to that point between 1 and the sims (as will be detailed below), rejecting otherwise. • It updates the simulated state information and moves the head corresponding to each sim in accordance with 1’s transition function, the latest public coin outcome, the input symbol scanned by the corresponding head and the communication symbol received from 2 addressed to that sim. • It sends 2 a 2-tuple containing the communication symbols emitted by all the sims at the present step.
The consistency check mentioned above is necessary for the following reason: Consider two distinct sims which correspond to two probabilistic paths that emit precisely the same sequence of communication symbols up to a certain point during an interaction of 1 with 1. Since 1 is unable to determine which of these two paths it is talking to at that point, it cannot send diferent communication symbols to these sims. 2 is supposed to check that 2 respects this condition, and never sends diferent symbols to two sims whose communications have been identical since the beginning of the interaction. 2 can keep track of subsets of such similar-looking sims in its finite memory to implement this control at every step.
2 uses its remaining heads to implement a deterministic clock that runs for 2() = steps (where is a positive integer whose value ensures that 2() ≫ 1(), and determines the error committed by 2, as will be described below) in the background.6 2 makes its decision when the clock times out by picking one of the sims at random with equal probability by the result of public coin tosses. It accepts if the chosen sim has accepted on time, and rejects otherwise.
2 is not able to carry out a “perfect” simulation of 1 (with identical acceptance and rejection probabilities) because of the strict bound on its runtime. This causes 2’s decisions to difer from those of 1 in the following two ways: 1. 1 has a nonzero probability of accepting some inputs after running for more than 2() steps, whereas 2 rejects in branches of its simulation corresponding to such cases. 2. 2 rejects and halts on each branch of its simulation corresponding to cases where 1 is tricked to run forever.
Let 2+ and −2 be the counterparts in 2 of the errors 1+ and −1 , respectively. (2 can not be fooled into looping, so we do not have to worry about that type of error.) Let us analyze how the two diferences described above afect the errors of 2 compared to those of 1. 6See [7, Lemma 3] for an explanation of how such a clock can be constructed for any desired value of .
−2 is at most −1 , since none of the diferences between 2 and 1 can cause an increase in an acceptance probability.
2+ is greater than 1+ by the probability that 1 runs longer than 2() steps and then accepts. By definition, the expected runtime of 1 is 1() when it is not running forever (i.e., with probability 1 − l1oop). By Markov’s inequality, the probability that 1 runs for more than 2() steps when it is not running forever is at most 1()/2(). This diference can be reduced by increasing , thus bringing 2+ arbitrarily close to 1+, and proving our claim that the overall error bound of 2 is close to that of 1.
We will conclude the proof by demonstrating 3, a standard public coin log-space verifier with a single input head that verifies the same language. The naive way of simulating a multi-head machine by a logarithmic space machine is rather straightforward. Specifically, 3 can keep 2’s head indices in multiple tracks of its work tape in binary format. (To accommodate for 2 + tracks in the work tape, 3 should use a work tape alphabet of size 22+.) In each simulated transition of 2, to decipher what 2 is reading with its 2 + heads, 3 will carry out the following steps:
2. Do the following for all ∈ { 1, . . . , 2 + }: 3. Decrement the index on the th track of the work tape and move the input head to the right. Repeat this until the index becomes 0. 4. Register the symbol under the input head as . 5. Increment the index on the th track of the work tape and move the input head to the left.
Repeat this until the head is reading ▷.
Having learned the symbols 1, . . . , 2+ scanned by the simulated 2’s heads, 3 can use the latest public coin flip and consult the communication cell to complete a simulated transition of 2, updating the work tape contents to reflect the new head positions of 2 by incrementing or decrementing the indices on the respective tracks. Note that the matching prover, 3, which is supposed to send the messages that 2 would be sending for each simulated step, will send “filler” symbols (all of which will be ignored by 3) through the communication cell while it waits for 3 to complete these walks on its work tape. 3 accepts the input only if it is convinced that 2 accepts the same as a result of this interaction.
3’s runtime is simply the runtime of 2 multiplied by the overhead of simulating multiple input heads within the logarithmic work tape. Counting from 0 to (or down from to 0) in binary takes O () time for a Turing machine by amortized analysis. Incrementing or decrementing binary numbers with ⌈log ⌉ digits takes O (log ) time. As a result, using the naive method of simulation explained above, 3 is expected to run in O (︀ +1)︀ time.
The runtime of 3 in Lemma 7 can be improved by introducing 2 + logarithmically-long caches in the memory, one for each head of the simulated 2, each containing the slice from the input string where the corresponding head resides at that time. This slightly more advanced way of simulating multiple heads using logarithmic space (which has been previously used and demonstrated in detail in [7]) saves 3 a factor of O (log ) in runtime, but we stuck with the naive method for its suficiency and simplicity.
Since log2 ∈ O () by standard asymptotic analysis, we also have
NC ⊆ IP(con-space, con-private-coins, O(︀ 4)︀ * -public-coins, O(︀ 4)︀ * -time).
NC ⊆ IP(log-space, 0-private-coins, O(︀ log2 )︀ -public-coins, O(︀ log2 )︀ -time).
NC ⊆ IP(log-space, 0-private-coins, O(︀ 2)︀ -public-coins, O(︀ 2)︀ -time).
Theorem 8.
This line of research can be expanded with various further questions. Although we mentioned the efect of cutting of the usage of public coins completely (Fact 4), we did not consider the results of imposing a tight budget on the number of public coins that the verifier can flip. (The “clock” head’s random walk in Section 2.4 has an expected cost of polynomially many such flips.) It would be interesting, for instance, to ask whether Condon and Ladner’s result stating that logarithmic space verifiers that flip only logarithmically many public coins can not verify any language outside the class LOGCFL [10] has a counterpart for the constant space case or not.
The authors thank the anonymous referees for their comments. This research was partially supported by Boğaziçi University Research Fund Grant Number 19441. Utkan Gezer’s participation in this work is supported by the Turkish Directorate of Strategy and Budget under the TAM Project number 2007K12-873. [6] M. U. Gezer, A. C. C. Say, Finite state verifiers with both private and public coins, arXiv e-prints (2023). arXiv:2306.09542. [7] M. U. Gezer, A. C. C. Say, Constant-space, constant-randomness verifiers with arbitrarily small error, Information and Computation 288 (2022) 104744. [8] A. Condon, Computational Models of Games, MIT Press, 1989. [9] L. Fortnow, C. Lund, Interactive proofs and alternating time-space complexity, Theoretical
Computer Science 113 (1993) 55–73. [10] A. Condon, R. Ladner, Interactive proof systems with polynomially bounded strategies, Journal of Computer and System Sciences 50 (1995) 506–518.