Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with forcing:
TR94-014 | 12th December 1994
Miklos Ajtai

The Independence of the modulo p Counting Principles

The modulo $p$ counting principle is a first-order axiom
schema saying that it is possible to count modulo $p$ the number of
elements of the first-order definable subsets of the universe (and of
the finite Cartesian products of the universe with itself) in a
consistent way. It trivially holds on ... more >>>

TR23-008 | 2nd February 2023
Ond?ej Ježil

Limits of structures and Total NP Search Problems

For a class of finite graphs, we define a limit object relative to some computationally restricted class of functions. The properties of the limit object then reflect how a computationally restricted viewer "sees" a generic instance from the class. The construction uses Krají?ek's forcing with random variables [7]. We prove ... more >>>

ISSN 1433-8092 | Imprint