about.

In general, I think the problem is that writers tend to be imprecise or like to

reword theorems/statements, but often introduce critical errors while doing so.

Also, if the writer does not know too much about a subject and is just reading

Wikipedia, there's great potential for adding non uniquely identifying or

misleading clues. In fact, almost any time I looked up a tossup with non

uniquely identifying clues, all the lines were sourced from Wikipedia, which

isn't bad necessarily, but can sometimes lead to bad questions.

My other complaint is that in a lot of tossups, it's just a bunch of statements

of theorems one after the other with no connection or sense of "big picture" or

philosophical importance. Why is the busy beaver important at all? It's not

clear from the tossup I later mention. But perhaps this isn't possible given

the format.

**ACF Nationals**

=================

ACF Nationals 2015 Round 16 Question 8

1) You can't really prove anything by reducing PCP to halting problem.Question: A value named for this scenario is defined as the sum over all inputs

p of "two raised to the negative of the absolute value of the length of p" and

is an example of a Martin-Lof random sequence. The proof of the principal

theorem resulting from this scenario relies on constructing a model whose two

inputs are another model of the same type as well a string, then having that

first model output the opposite of the second model; afterwards it is shown

that there is a contradiction if both models are the same. A reduction of this

scenario is used to prove that computing a non-trivial partial function is

impossible, a result known as Rice's theorem. Chaitin's constant gives the

probability that a program successfully resolves this scenario. The

insolvability of the Post correspondence problem relies on reducing it to this

other problem. For 10 points, name this undecidable decision problem which asks

if a Turing Machine will stop for a given input.

ANSWER: halting problem

The question meant to say "..relies on reducing this problem to PCP".

Common mistake but it makes the clue completely wrong.

2) Acceptance problem for Turing machines (rather than halting) is usually

reduced to PCP, though they are closely related. Acceptance problem should

probably just be an alternate answer.

=================

ACF Nationals 2016 Round Michigan B Question 2

ANSWER: Busy beaver function

1) The statement that BB(5) = 4098 is incorrect, this is just a lower bound

2) In general this tossup doesn't talk about why the Busy Beaver is

computationally or philosophically important, it just lists a bunch of big

numbers. But maybe it's hard to motivate it while still being uniquely

identifying.

=================

ACF Nationals 2014 Round Michigan Bonus 4

ANSWER: Post correspondence problem

1) This is a really bad description of the PCP, and I don't think it can be

considered remotely correct even given generous interpretation.

=================

ACF Nationals 2011 Round Yale Tossup 14

ANSWER: DFAs

1) "A set of symbols...in the language" is not unique to DFAs at all, that's

basically the definition of the language of any machine

2) The pumping lemma doesn't state that DFAs can't recognize nonregular

languages. Rather, regular languages are defined as languages that can be

recognized by DFAs.

3) "These objects can be defined with a finite alphabet, a set of states, and a

transition function...". This is also true for PDAs, deterministic PDAs, LBAs,

Turing machines, whatever. Not unique at all.

4) The tossup should most likely accept or at least prompt on NFAs since a

large part of the clues involve constructions that use NFAs.

=================

**Chicago Open**

=================

Chicago Open 2010 Round 3 Question 2

ANSWER: interactive proof

1) Completeness and soundness are bounded by 2/3 and 1/3 respectively, usually,

not 1/3 and 2/3 like the question says.

2) The question implies AM[poly(n)] = AM[2], which is still an open problem).

It is true however that AM[k] = AM[2] for constant k. Problem is that

"Arthur-Merlin protocol" doesn't really clearly correspond to any of AM, MA,

AM[k], or AM[poly(n)].

3) Many interactive proofs don't involve any sort of committing as the question

implies, but zero-knowledge proofs do due to Goldwasser,

Sipser et al. - maybe this is what the author meant. However note that

their construction involves commitment schemes, and I think all

committment schemes assume that one-way functions exist, which is not known

to be the case, so it doesn't really make sense to make such a blanket statement.

4) The prover is not usually probabilistic, since he has infinite power (or in

some cases, limited to PSPACE), he can just simulate randomness. In fact, many

constructions of IP model the prover as a function instead of a Turing machine.

5) In interactive proofs, the verifier is never dishonest. However the verifier

could be dishonest in zero knowledge proofs.

6) Shamir seems pretty early given the difficulty of the following clues.

=================

Chicago Open 2016 Round 11a Mukherstein Question 14

ANSWER: oracle machines

1) I could be wrong but I don't think the prononuciation of languages with

oracle machines L^A as "L-A" is standard (at least my professor says "L to the

A"). Might trip up a few people who intepret it as L(A).

=================G

**ACF Regionals**

=================

ACF Regionals 2015 Round VCU A + Dorman HS Question 17

1) Concatenation, union, and Kleene star apply to languages in general, notQuestion: The cycle rank, or loop complexity, of a directed graph is related to

a quantity for these things according to a theorem devised by Eggan. These

things can be converted to an NFA by constructing partial NFAs and putting them

together with an epsilon transition, as is done by Thompson's construction

algorithm. Like a namesake type of language, these things were developed and

formalized by Stephen Kleene, who defined concatenation, union, and his

namesake star for them. A backreference in these things can be created using

parentheses. The asterisk quantifier is used to match the previous group or

character zero or more times in Perl's system for them. For 10 points, identify

these notations used for pattern matching that describe a set of strings,

so-called "expressions".

ANSWER: regular expressions [or regexp; or regular sets; or rational

expressions; or regular languages; accept just regular after "expressions" is

read; prompt on "patterns"]

just regular languages.

2) Backreferences are impossible in "real" regular expressions. Maybe "A

backreference in a generalization of one of these things" would be more

appropriate.

=================

ACF Regionals 2015 Round xEMERGENCY EXTRASx Question 3

1) Church-Turing thesis states that all algorithms computable in general (forQuestion: Langston's ant and turmites are two-dimensional analogues of these

constructs. Recursively enumerable languages are equivalent to the class of

languages recognized by these constructs. The universal variant of these

constructs can simulate every possible one of these constructs. Attaching one

of these to an "oracle" can make it stronger, and a busy beaver is a specific

variant of these constructs that executes the maximum number of steps. Lambda

calculus is equivalent in power to these constructs according to a hypothesis

named after Alonzo Church and these devices' namesake. For 10 points, name

these theoretical devices with a head that can read, write, and move upon an

infinite length of tape.

ANSWER: Turing machines

example, by a human) can be computed by Turing machines. Equivalence between

lambda calculus and Turing machines has been proved.

=================

ACF Regionals 2012 Round MIT A Question 2

ANSWER: NP

1) Again, it's not really clear what "Arthur Merlin" proof refers to.

=================

Lederberg 2014

All great, at least on the stuff I know.

-The compilers tossup was pretty easy, GHC and LLVM on second line.

-Java, I thought autoboxing was pretty basic stuff beginners learn

-Stable marriage is worded somewhat confusingly.

-Post question is good.

-Cryptographic keys tossup seems very easy compared to for example, planar

graphs or permutations.

=================

Avogadro 2016

All great, at least on the stuff I know.

1) Lawson's flip algorithm seems early mention, since the projection later

mentioned is used to prove the correctness of Lawson flip.

2) File question is good, but the "one of these things following a greater than

sign" probably confused some people. Maybe "the name of one of these things"

would be better. I think more people would be familiar with the 3 UNIX

permissions octals than the specific ext3/ext4 implementations.

3) "hacking" xkcd clue is nice

=================

George Oppen Round 15 Question TB Bonus

ANSWER: Boolean satisfiability

1) The answerline accepts 2-SAT as an alternate answer, which is incorrect

since 2-SAT is known to be in P and even NL.

=================

MUT 2012 Round 3 Question 18

ANSWER: P

1) The bonus lead in says that we are sure P!=PSPACE. However, this is an

open question.

=================

For fun,

ACF Nationals 2004 Round Rutgers Question 23

1) QSAT is not the typical name for the canonical PSPACE-complete problem, it's

called TQBF by almost everyone but one specific textbook, that isn't a major

one. Further, the description of TQBF is incorrect, because "satisfiability of

first-order logical expressions" is undecidable in general. In TQBF, variables

are quantified over the set {0, 1}.

2) Graph non-isomorphism is in PSPACE, sure, but any reasonable person would

say it's in co-NP, since it is way more specific than PSPACE.

3) P also trivially includes L, though I believe P=L is still open. NL, P, and

NP could also reasonably be proper subsets of Sigma2, PH, #P, EXP, NEXP, some

circuit classes, whatever.

=================

Also, why are there so many clues on Chaitin's constant? Fuck Chaitin's

constant.