Checkers for Adaptive Programs

スポンサーリンク

概要

• 論文の詳細を見る

• Let L ⫅ {0,1} be a language and let λ_L : {0,1} ↦ {0,1} be the characteristic function of the language L, i.e., if x∈L, λ_L(x)=1 ; otherwise, λ_L(x)=0. In this paper, we consider an adaptive checker with a single program F^* (resp. noncommunicating multiple programs F^*_1, F^*_2,...) for λ_L that works even when an incorrect program F^* (resp. incorrect noncommunicating multiple programs F^*_1, F^*_2,...) for λ_L adaptively behaves according to inputs previously provided to the program F^* (resp. the programs F^*_1, F^*_2,...). We show that (1) for any language L, there exists an adaptive checker with a single program for λ_L iff L and L respectively have competitive interactive proof systems ; and (2) that for any language L, there exists an adaptive checker with noncommunicating multiple programs for λ_L iff L and L respectively have function-restricted interactive proof systems. This implies that for any language L, adaptive checkers with noncommunicating multiple programs for λ_L are as powerful as static ones with a single program for λ_L.

• 社団法人電子情報通信学会の論文
• 1995-01-25

著者

• Takei M

  Department Of Mechanical Engineering Nihon University

• Takei Masahiro

  Interdisciplinary Graduate School Of Science And Engineering Tokyo Institute Of Technology

• Itoh Toshiya

  Interdisciplinary Graduate School Of Science And Engineering Tokyo Institute Of Technology

関連論文

• Reconstruction of Free Fall Particle CT Images Using the Generalized Vector Sampled Pattern Matching Method
• Particle Image Velocimetry Using Wavelet Multi-resolution Analysis
• Wavelet Analysis of Turbulent Structures in Far Wake (第30回可視化情報シンポジウム講演論文集) -- (オーガナイズドセッション ウェーブレットと知的可視化の応用 4)
• Visualization of Multi-Scale Structures for Differential Conditions of Turbulent Wake Using Wavelets (第29回 可視化情報シンポジウム講演論文集) -- (ウェーブレットと知的可視化の応用 (2))
• Wavelet Multiresolution Analysis Applied to Coherent Structure Eduction of a Turbulent Jet
• Eduction of Unsteady Structure in a Turbulent Jet by Use of Continuous and Discrete Wavelet Transforms
• Analysis of Pressure Signal in a Gas-Solid Two-Phase flow Based on Discrete Wavelet Transform (第28回 可視化情報シンポジウム講演論文集) -- (オーガナイズドセッション:ウエーブレットの応用(4))
• PIV based on Wavelet Packet Image Compression Technique (第28回 可視化情報シンポジウム講演論文集) -- (オーガナイズドセッション:ウエーブレットの応用(4))
• Application of Two-Dimensional Orthogonal Wavelets to Multiresolution Image Analysis of a Turbulent Jet
• Analysis of Turbulent Structure Using Discrete Wavelet Transform (第27回可視化情報シンポジウム講演論文集)
• PIV Standard Image compression based on Wavelet Transform (第27回可視化情報シンポジウム講演論文集)
• Wavelets:Challenges for Fluids Engineering (第27回可視化情報シンポジウム講演論文集)
• Multiresolution Visualization of the Turbulent Jet
• Visualization of Multi-Scale Turbulent Structures Using Orthogonal Wavelet Transform
• Checkers for Adaptive Programs
• Alternative Necessary and Sufficient Conditions for Collision Intractable Hashing
• A Note on AM Languages Outside NP ⋃ co-NP (Special Section on Cryptography and Information Security)
• Demonstrating Possession without Revealing Factors (Special Section on Cryptography and Information Security)
• On the Power of Self-Testers and Self-Correctors (Special Section on Cryptography and Information Security)
• On the Knowledge Tightness of Zero-Knowledge Proofs (Special Section on Cryptography and Information Security)
• Efficient Private Information Retrieval (Special Section on Cryptography and Information Security)
• On the Oracle Entropy and the Average Case Oracle Measure of Knowledge Complexity (Special Section on Cryptography and Information Security)
• On the Knowledge Complexity of Arthur-Merlin Games (Special Section on Cryptography and Information Security)

もっと見る 閉じる

スポンサーリンク