6533b7ddfe1ef96bd1273f7d
RESEARCH PRODUCT
On Horn spectra
Wiesław Szwastsubject
Class (set theory)NEXPTIMEGeneral Computer ScienceFrench hornComputabilitySpectrum (functional analysis)EXPTIMEOracleTheoretical Computer ScienceCombinatoricsComputer Science::Logic in Computer ScienceComputer Science::Formal Languages and Automata TheoryComputer Science(all)Generator (mathematics)Mathematicsdescription
Abstract A Horn spectrum is a spectrum of a Horn sentence. We show that to solve Asser's problem, and consequently the EXPTIME = ? NEXPTIME question it suffices to consider the class of Horn spectra. We also pose the problem whether or not the generator of every Horn spectrum is a spectrum. We prove that from a negative solution of the generator problem, a negative answer for the EXPTIME = ? NEXPTIME question follows. Some other relations between the generator problem and Asser's problem are given. Finally, the relativized version of the generator problem is formulated and it is shown that it has an affirmative solution for some oracles, and a negative solution for some others.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1991-05-01 | Theoretical Computer Science |