找回密码
 To register

QQ登录

只需一步,快速开始

扫一扫,访问微社区

Titlebook: Structure in Complexity Theory; Proceedings of the C Alan L. Selman Conference proceedings 1986 Springer-Verlag Berlin Heidelberg 1986 Arit

[复制链接]
楼主: miserly
发表于 2025-3-28 15:03:46 | 显示全部楼层
发表于 2025-3-28 19:43:12 | 显示全部楼层
Relativized alternation,epends on the oracle. Such results are commonly taken as evidence of the difficulty of solving the unrelativized case, on the assumption that simple simulations and diagonalizations generalize to oracle machines. However, some simple simulations, such as the alternation theorems of Chandra, Kozen an
发表于 2025-3-28 23:10:25 | 显示全部楼层
The polynomial hierarchy and intuitionistic Bounded Arithmetic, the polynomial hierarchy. This is an extension of earlier work on the classical Bounded Arithmetic and was first conjectured by S. Cook. In contrast to the classical theories of Bounded Arithmetic where Σ.-definable functions are of interest, our results for intuitionistic theories concern all the
发表于 2025-3-29 04:45:40 | 显示全部楼层
发表于 2025-3-29 08:22:20 | 显示全部楼层
发表于 2025-3-29 13:43:11 | 显示全部楼层
Probabilistic game automata, [1] andthe interactive proof systems of Goldwasser, Micali and Rackoff [5]. We prove a number of results about another special case, ., which is a generalization of games against nature. In our notation, we let .(., resp.) denote the class of two-person games with unbounded two-sided error where on
发表于 2025-3-29 19:22:49 | 显示全部楼层
发表于 2025-3-29 20:03:30 | 显示全部楼层
Resource-bounded Kolmogorov complexity of hard languages,is introduced. Among others we show that there exists a language L in DTIME(2.) such that the 2.-time-bounded Kolmogorov complexity of L is exponential almost everywhere. We study time-/space- bounded Kolmogorov complexity of languages that are DTIME(2.)-(SPACE (2.)-) hard under polynomial-time Turi
发表于 2025-3-30 00:48:44 | 显示全部楼层
What is a hard instance of a computational problem?,y, an instance x is considered to be hard for a problem A if every algorithm that decides A and runs "fast" on x needs to look up (a description of) x in a table. A main result states that all problems not in P have infinitely many (polynomially) hard instances. Further, there exist problems in EXPT
发表于 2025-3-30 05:27:06 | 显示全部楼层
 关于派博传思  派博传思旗下网站  友情链接
派博传思介绍 公司地理位置 论文服务流程 影响因子官网 SITEMAP 大讲堂 北京大学 Oxford Uni. Harvard Uni.
发展历史沿革 期刊点评 投稿经验总结 SCIENCEGARD IMPACTFACTOR 派博系数 清华大学 Yale Uni. Stanford Uni.
|Archiver|手机版|小黑屋| 派博传思国际 ( 京公网安备110108008328) GMT+8, 2025-6-5 21:20
Copyright © 2001-2015 派博传思   京公网安备110108008328 版权所有 All rights reserved
快速回复 返回顶部 返回列表