論理関数の内包関数と外包関数について

  • Makino Kazuhisa
    Department of Applied Mathematics and physics,Faculty of Engineering,Kyoto University
  • Ibaraki Toshihide
    Department of Applied Mathematics and physics,Faculty of Engineering,Kyoto University

Bibliographic Information

Other Title
  • Interior and Exterior Functions of Boolean Functions

Search this article

Description

本論文では,論理関数fの安定性を考察するためにfの内包関数,外包関数,および,層を定義し,この定義に関連したINTERIOR,EXTERIOR,LAYERの3つの問題を考えます.まず,fを正関数に限定しても,問題LAYERが,NP困難であること,および,P≠NPならば,問題INTERIORとEXTERIORに対する多項式時間アルゴリズムが存在しないことを示しました.しかしながら,2単調正関数においては,問題LAYERが多項式時間で解くことができること,さらに,問題INTERIORとEXTERIORに対する逐次多項式アルゴリズムの存在を示しました.
We define the interior functions,exterior functions and layers of a Boolean function f in order to investigate its stability,and consider three problems INTERIOR,EXTERIOR and LAYER associated with such definitions.We show that even if f is restricted to be a positive function,LAYER is NP-hard and there is no polynomial total time algorithm,unless P=NP,for INTERIOR and EXTERIOR.However, for a 2-monotonic positive function f,LAYER can be solved in polynomial time and there exist incrementally polynomial algorithms for INTERIOR and EXTERIOR.

Journal

Keywords

Details 詳細情報について

  • CRID
    1573387452166654208
  • NII Article ID
    110003191725
  • NII Book ID
    AN10013152
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top