holographic algorithms by fibonacci gates and holographic reductions for hardness

ISCAS OpenIR

	holographic algorithms by fibonacci gates and holographic reductions for hardness
	Cai Jin-Yi; Lu Pinyan; Xia Mingji
	2008
会议名称	49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
会议录名称	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
页码	644-653
会议日期	40841
会议地点	Philadelphia, PA, United states
收录类别	ei
出版地	United States
ISSN	2725428
ISBN	9780769534367
部门归属	(1) Computer Sciences Department, University of Wisconsin-Madison, Harvard University; (2) Institute for Theoretical Computer Science, Tsinghua University; (3) Institute of Software, Chinese Academy of Sciences
摘要	We propose a new method to prove complexity dichotomy theorems. First we introduce Fibonacci gates which provide a new class of polynomial time holographic algorithms. Then we develop holographic reductions. We show that holographic reductions followed by
关键词	Computers Hardness Optical Devices Polynomial Approximation
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/10462
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Cai Jin-Yi,Lu Pinyan,Xia Mingji. holographic algorithms by fibonacci gates and holographic reductions for hardness[C]. United States,2008:644-653.