未找到相关数据
Separability and one-way functions
被引：0
作者：
Lance Fortnow
John D. Rogers
机构：
[1] University of Chicago,Computer Science Department
[2] DePaul University,School of CTI
来源：
computational complexity
|
2002年
/
11卷
关键词：
Structural complexity;
relativization;
generic oracles;
68Q15;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We settle all relativized questions of the relationships between
the following five propositions:
P = NP.P = UP.P = NP $\cap$ coNP.All disjoint pairs of NP sets are P-separable.All disjoint pairs of coNP sets are P-separable.
We make the first widespread use of variations of generic oracles to
achieve the necessary relativized worlds.
引用
收藏
页码：137 / 157
页数：20
相关论文