Results for ' 68Q15'

5 found
Order:
  1.  8
    A Minimal Set Low for Speed.Rod Downey & Matthew Harrison-Trainor - 2022 - Journal of Symbolic Logic 87 (4):1693-1728.
    An oracle A is low-for-speed if it is unable to speed up the computation of a set which is already computable: if a decidable language can be decided in time $t(n)$ using A as an oracle, then it can be decided without an oracle in time $p(t(n))$ for some polynomial p. The existence of a set which is low-for-speed was first shown by Bayer and Slaman who constructed a non-computable computably enumerable set which is low-for-speed. In this paper we answer (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  2.  11
    On the Existence of Strong Proof Complexity Generators.Jan Krajíček - 2024 - Bulletin of Symbolic Logic 30 (1):20-40.
    Cook and Reckhow [5] pointed out that $\mathcal {N}\mathcal {P} \neq co\mathcal {N}\mathcal {P}$ iff there is no propositional proof system that admits polynomial size proofs of all tautologies. The theory of proof complexity generators aims at constructing sets of tautologies hard for strong and possibly for all proof systems. We focus on a conjecture from [16] in foundations of the theory that there is a proof complexity generator hard for all proof systems. This can be equivalently formulated (for p-time (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  3.  37
    New Relations and Separations of Conjectures About Incompleteness in the Finite Domain.Erfan Khaniki - 2022 - Journal of Symbolic Logic 87 (3):912-937.
    In [20] Krajíček and Pudlák discovered connections between problems in computational complexity and the lengths of first-order proofs of finite consistency statements. Later Pudlák [25] studied more statements that connect provability with computational complexity and conjectured that they are true. All these conjectures are at least as strong as $\mathsf {P}\neq \mathsf {NP}$ [23–25].One of the problems concerning these conjectures is to find out how tightly they are connected with statements about computational complexity classes. Results of this kind had been (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  4.  27
    Do there exist complete sets for promise classes?Olaf Beyersdorff & Zenon Sadowski - 2011 - Mathematical Logic Quarterly 57 (6):535-550.
    In this paper we investigate the following two questions: Q1: Do there exist optimal proof systems for a given language L? Q2: Do there exist complete problems for a given promise class equation image?For concrete languages L and concrete promise classes equation image , these questions have been intensively studied during the last years, and a number of characterizations have been obtained. Here we provide new characterizations for Q1 and Q2 that apply to almost all promise classes equation image and (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  5.  12
    The wadge order on the Scott domain is not a well-quasi-order.Jacques Duparc & Louis Vuilleumier - 2020 - Journal of Symbolic Logic 85 (1):300-324.
    We prove that the Wadge order on the Borel subsets of the Scott domain is not a well-quasi-order, and that this feature even occurs among the sets of Borel rank at most 2. For this purpose, a specific class of countable 2-colored posets$\mathbb{P}_{emb} $equipped with the order induced by homomorphisms is embedded into the Wadge order on the$\Delta _2^0 $-degrees of the Scott domain. We then show that$\mathbb{P}_{emb} $admits both infinite strictly decreasing chains and infinite antichains with respect to this (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark