NDLI: Resource-Bounded Kolmogorov Complexity Revisited

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Buhrman, Harry Laplante, Sophie Fortnow, Lance
Copyright Year	2002
Abstract	We take a fresh look at CD complexity, where CDt (x) is the size of the smallest program that distinguishes x from all other strings in time t(\|x\|). We also look at CND complexity, a new nondeterministic variant of CD complexity, and time-bounded Kolmogorov complexity, denoted by C complexity.We show several results relating time-bounded C, CD, and CND complexity and their applications to a variety of questions in computational complexity theory, including the following: Showing how to approximate the size of a set using CD complexity without using the random string as needed in Sipser's earlier proof of a similar result. Also, we give a new simpler proof of this result of Sipser's. Improving these bounds for almost all strings, using extractors. A proof of the Valiant--Vazirani lemma directly from Sipser's earlier CD lemma. A relativized lower bound for CND complexity. Exact characterizations of equivalences between C, CD, and CND complexity. Showing that satisfying assignments of a satisfiable Boolean formula can be enumerated in time polynomial in the size of the output if and only if a unique assignment can be found quickly. This answers an open question of Papadimitriou. A new Kolmogorov complexity-based proof that BPP\subseteq\Sigma_2^p$. New Kolmogorov complexity based constructions of the following relativized worlds: There exists an infinite set in P with no sparse infinite NP subsets. EXP=NEXP but there exists a NEXP machine whose accepting paths cannot be found in exponential time. Satisfying assignments cannot be found with nonadaptive queries to SAT.
Starting Page	887
Ending Page	905
Page Count	19
File Format	PDF
ISSN	00975397
DOI	10.1137/S009753979834388X
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3
Volume Number	31
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2001-01-01
Access Restriction	Subscribed
Subject Keyword	Kolmogorov complexity CD complexity computational complexity Complexity classes Algorithmic information theory
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Compressibility and Resource Bounded Measure

Category and Measure in Complexity Classes

Resource-Bounded Kolmogorov Complexity Revisited (1997)

Algorithmic statistics revisited

Inequalities for space-bounded Kolmogorov complexity

Resource-Bounded Kolmogorov Complexity Revisited (2001)

Plain stopping time and conditional complexities revisited

An additivity theorem for plain Kolmogorov complexity

Kolmogorov Complexity of Categories

Resource-Bounded Kolmogorov Complexity Revisited

Similar Documents

Compressibility and Resource Bounded Measure

Category and Measure in Complexity Classes

Resource-Bounded Kolmogorov Complexity Revisited (1997)

Algorithmic statistics revisited

Inequalities for space-bounded Kolmogorov complexity

Resource-Bounded Kolmogorov Complexity Revisited (2001)

Plain stopping time and conditional complexities revisited

An additivity theorem for plain Kolmogorov complexity

Kolmogorov Complexity of Categories

Resource-Bounded Kolmogorov Complexity Revisited