Title :
Resource-bounded continuity and sequentiality for type-two functionals
Author :
Buss, Samuel R. ; Kapron, Bruce M.
Author_Institution :
Dept. of Math., California Univ., San Diego, La Jolla, CA, USA
Abstract :
We define notions of resource-bounded continuity and sequentiality for type-two functionals with total inputs, and prove that in the resource-bounded model there are continuous functionals which cannot be efficiently simulated by sequential functionals. We also show that for some naturally defined classes of continuous functionals, an efficient simulation is possible
Keywords :
Boolean functions; computability; computational complexity; decision trees; Boolean functions; computability; continuous functionals; decision tree complexity; resource-bounded continuity; resource-bounded model; sequential functionals; sequentiality; simulation; type-two functionals; Boolean functions; Computational complexity; Computational modeling; Computer languages; Computer science; Computer simulation; Decision trees; History; Mathematics; Surface-mount technology;
Conference_Titel :
Logic in Computer Science, 2000. Proceedings. 15th Annual IEEE Symposium on
Conference_Location :
Santa Barbara, CA
Print_ISBN :
0-7695-0725-5
DOI :
10.1109/LICS.2000.855757
