P ≠ NP ∧ co-NP for infinite time Turing machines

被引：14

作者：

Deolalikar, V

Hamkins, JD

Schindler, R

机构：

[1] Hewlett Packard Res, Palo Alto, CA 94304 USA

[2] CUNY Coll Staten Isl, New York, NY 10016 USA

[3] CUNY Grad Ctr, Math Program, New York, NY 10016 USA

[4] Univ Munster, Inst Math Log & Grundlagenforsch, D-48149 Munster, Germany

来源：

JOURNAL OF LOGIC AND COMPUTATION | 2005年 / 15卷 / 05期

基金：

美国国家科学基金会;

关键词：

infinite time Turing machines; complexity theory; descriptive set theory;

D O I：

10.1093/logcom/exi022

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Extending results of Schindler, Hamkins and Welch, we establish in the context of infinite time Turing machines that P is properly contained in NP boolean AND co-NP. For higher analogues of these classes, we exhibit positive and negative results.

引用

页码：577 / 592

页数：16

共 11 条

[1]

[Anonymous], 1985, OXFORD LOGIC GUIDES

[2]

Barwise J., 1975, PERSPECTIVES MATH LO

[3] Infinite time Turing machines [J].

Hamkins, JD ;

Lewis, A .

JOURNAL OF SYMBOLIC LOGIC, 2000, 65 (02) :567-604

[4] Pf≠NPf for almost all f [J].

Hamkins, JD ;

Welch, PD .

MATHEMATICAL LOGIC QUARTERLY, 2003, 49 (05) :536-540

[5]

Kechris A, 1995, GRADUATE TEXTS MATH

[6]

Moschovakis Y.N., 1980, Studies in Logic and the Foundations of Mathematics, V100

[7] P ≠ NP for infinite time Turing machines [J].

Schindler, R .

MONATSHEFTE FUR MATHEMATIK, 2003, 139 (04) :335-340

[8]

WELCH P, UNPUB ARITHMETICAL Q

[9]

WELCH P, 2005, IN PRESS CIE LNCS VO

[10]

WELCH P, QUESTION DEOLALIKAR

← 1 2 →