首页 | 本学科首页   官方微博 | 高级检索  
     检索      


A note on parallel and alternating time
Authors:Felipe Cucker  Irne Briquel
Institution:aDepartment of Mathematics, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong;bLaboratoire d’Informatique et de Parallélisme, ENS Lyon 46, allée d’Italie, 69364 Lyon Cedex 07, France
Abstract:A long standing open question in complexity theory over the reals is the relationship between parallel time and quantifier alternation. It is known that alternating digital quantifiers is weaker than parallel time, which in turn is weaker than alternating unrestricted (real) quantifiers. In this note we consider some complexity classes defined through alternation of mixed digital and unrestricted quantifiers in different patterns. We show that the class of sets decided in parallel polynomial time is sandwiched between two such classes for different patterns.
Keywords:Complexity classes  Parallelism  Alternation
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号