All reports by Author Ond?ej Ježil:

__
TR23-008
| 2nd February 2023
__

Ond?ej Ježil#### Limits of structures and Total NP Search Problems

Ond?ej Ježil

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 >>>