A. C. Cem Say
Causes of Ineradicable Spurious Predictions in Qualitative Simulation.
Tue, 10/04/2011 - 15:01 — SomNambulAuthors: A. C. Cem Say, O. Yilmaz
Subjects: Artificial Intelligence
AbstractIt was recently proved that a sound and complete qualitative simulator does
not exist, that is, as long as the input-output vocabulary of the
state-of-the-art QSIM algorithm is used, there will always be input models
which cause any simulator with a coverage guarantee to make spurious
predictions in its output. In this paper, we examine whether a meaningfully
expressive restriction of this vocabulary is possible so that one can build a
simulator with both the soundness and completeness properties.NP has log-space verifiers with fixed-size public quantum registers.
Fri, 01/28/2011 - 16:01 — SomNambulAuthors: A. C. Cem Say, Abuzer Yakaryilmaz
Subjects: Computational Complexity
AbstractIn classical Arthur-Merlin games (AM), the class of languages whose
membership proofs can be verified by Arthur using logarithmic space coincides
with the class P \cite{Co89}. In this note, we show that if Arthur has a
fixed-size quantum register (the size of the register does not depend on the
length of the input) instead of another source of random bits, membership in
any language in NP can be verified with any desired error bound.- 8 comments
- login or register to post comments
Quantum function computation using sublogarithmic space (abstract & poster).
Fri, 09/17/2010 - 15:02 — SomNambulAuthors: A. C. Cem Say, Abuzer Yakaryilmaz
Subjects: Computational Complexity
AbstractWe prove that quantum Turing machines are strictly superior to probabilistic
Turing machines in function computation for any space bound $ o(\log(n)) $.- 7 comments
- login or register to post comments
User login
