On the Oracle Entropy and the Average Case Oracle Measure of Knowledge Complexity

Toshiya ITOH

On the Oracle Entropy and the Average Case Oracle Measure of Knowledge Complexity

Toshiya ITOH

Full Text Views

0

Cite this

Summary :

In this paper, we investigate statistical and perfect Knowledge Complexity (KC) with respect ot oracle entropy and average case oracle measures. As main results. we show the following: (1) for any k(n) 1/poly (n), if a language L has perfect KC k(n) + n^-ω(1) with respect to oracle entropy measure, then L has perfect KC k(n) with respect to oracle entropy measure (Theorem 3.1); (2) for any k(n) 1/poly(n), if a language L has perfect KC k(n) + n^-ω(1) with respect to average case oracle measure, then L has perfect KC k(n) with respect to average case oracle measure (Theorem 3.2); (3) if a language L has statistical KC k(n) ο(1) with respect to oracle entropy measure, then for any ε > 0, L has statistical KC k(n) + 1 + ε with respect to average case oracle measure (Theorem 4.1); and (4) if a language L has perfect KC k(n) ο(1) with respect to oracle entropy measure, then for any ε > 0, L has perfect KC k(n) + 2 + ε with respect to average case oracle measure (Theorem 4.2).

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.1 pp.90-97

Publication Date: 1997/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category

Cite this

Copy

Toshiya ITOH, "On the Oracle Entropy and the Average Case Oracle Measure of Knowledge Complexity" in IEICE TRANSACTIONS on Fundamentals, vol. E80-A, no. 1, pp. 90-97, January 1997, doi: .
Abstract: In this paper, we investigate statistical and perfect Knowledge Complexity (KC) with respect ot oracle entropy and average case oracle measures. As main results. we show the following: (1) for any k(n) 1/poly (n), if a language L has perfect KC k(n) + n^-ω(1) with respect to oracle entropy measure, then L has perfect KC k(n) with respect to oracle entropy measure (Theorem 3.1); (2) for any k(n) 1/poly(n), if a language L has perfect KC k(n) + n^-ω(1) with respect to average case oracle measure, then L has perfect KC k(n) with respect to average case oracle measure (Theorem 3.2); (3) if a language L has statistical KC k(n) ο(1) with respect to oracle entropy measure, then for any ε > 0, L has statistical KC k(n) + 1 + ε with respect to average case oracle measure (Theorem 4.1); and (4) if a language L has perfect KC k(n) ο(1) with respect to oracle entropy measure, then for any ε > 0, L has perfect KC k(n) + 2 + ε with respect to average case oracle measure (Theorem 4.2).
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_1_90/_p

Copy

@ARTICLE{e80-a_1_90,
author={Toshiya ITOH, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Oracle Entropy and the Average Case Oracle Measure of Knowledge Complexity},
year={1997},
volume={E80-A},
number={1},
pages={90-97},
abstract={In this paper, we investigate statistical and perfect Knowledge Complexity (KC) with respect ot oracle entropy and average case oracle measures. As main results. we show the following: (1) for any k(n) 1/poly (n), if a language L has perfect KC k(n) + n^-ω(1) with respect to oracle entropy measure, then L has perfect KC k(n) with respect to oracle entropy measure (Theorem 3.1); (2) for any k(n) 1/poly(n), if a language L has perfect KC k(n) + n^-ω(1) with respect to average case oracle measure, then L has perfect KC k(n) with respect to average case oracle measure (Theorem 3.2); (3) if a language L has statistical KC k(n) ο(1) with respect to oracle entropy measure, then for any ε > 0, L has statistical KC k(n) + 1 + ε with respect to average case oracle measure (Theorem 4.1); and (4) if a language L has perfect KC k(n) ο(1) with respect to oracle entropy measure, then for any ε > 0, L has perfect KC k(n) + 2 + ε with respect to average case oracle measure (Theorem 4.2).},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - On the Oracle Entropy and the Average Case Oracle Measure of Knowledge Complexity
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 90
EP - 97
AU - Toshiya ITOH
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1997
AB - In this paper, we investigate statistical and perfect Knowledge Complexity (KC) with respect ot oracle entropy and average case oracle measures. As main results. we show the following: (1) for any k(n) 1/poly (n), if a language L has perfect KC k(n) + n^-ω(1) with respect to oracle entropy measure, then L has perfect KC k(n) with respect to oracle entropy measure (Theorem 3.1); (2) for any k(n) 1/poly(n), if a language L has perfect KC k(n) + n^-ω(1) with respect to average case oracle measure, then L has perfect KC k(n) with respect to average case oracle measure (Theorem 3.2); (3) if a language L has statistical KC k(n) ο(1) with respect to oracle entropy measure, then for any ε > 0, L has statistical KC k(n) + 1 + ε with respect to average case oracle measure (Theorem 4.1); and (4) if a language L has perfect KC k(n) ο(1) with respect to oracle entropy measure, then for any ε > 0, L has perfect KC k(n) + 2 + ε with respect to average case oracle measure (Theorem 4.2).
ER -