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.