Separable discrete functions: Recognition and sufficient conditions

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10407349" target="_blank" >RIV/00216208:11320/19:10407349 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=9rdw_zRayV" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=9rdw_zRayV</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.disc.2018.12.026" target="_blank" >10.1016/j.disc.2018.12.026</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Separable discrete functions: Recognition and sufficient conditions

Popis výsledku v původním jazyce

A discrete function of n variables is a mapping g : X-1 x . . . x X-n -&gt; A, where X-1, . . . , X-n, and A are arbitrary finite sets. Function g is called separable if there exist n functions g(i) : X-i -&gt; A for i = 1, . . . , n, such that for every input x(1), . . . , x(n) the function g(x(1), . . . , x(n)) takes one of the values g(1)(x(1)), . . . , g(n)(x(n)). Given a discrete function g, it is an interesting problem to ask whether g is separable or not. Although this seems to be a very basic problem concerning discrete functions, the complexity of recognition of separable discrete functions of n variables is known only for n = 2. In this paper we will show that a slightly more general recognition problem, when g is not fully but only partially defined, is NP-complete for n &gt;= 3. We will then use this result to show that the recognition of fully defined separable discrete functions is NP-complete for n &gt;= 4. The general recognition problem contains the above mentioned special case for n = 2. This case is well-studied in the context of game theory, where (separable) discrete functions of n variables are referred to as (assignable) n-person game forms. There is a known sufficient condition for assignability (separability) of two-person game forms (discrete functions of two variables) called (weak) total tightness of a game form. This property can be tested in polynomial time, and can be easily generalized both to higher dimension and to partially defined functions. We will prove in this paper that weak total tightness implies separability for (partially defined) discrete functions of n variables for any n, thus generalizing the above result known for n = 2. Our proof is constructive. Using a graph-based discrete algorithm we show how for a given weakly totally tight (partially defined) discrete function g of n variables one can construct separating functions g(1), . . . , g(n) in polynomial time with respect to the size of the input function. (C) 2019 Elsevier B.V. All rights reserved.

Název v anglickém jazyce

Separable discrete functions: Recognition and sufficient conditions

Popis výsledku anglicky

A discrete function of n variables is a mapping g : X-1 x . . . x X-n -&gt; A, where X-1, . . . , X-n, and A are arbitrary finite sets. Function g is called separable if there exist n functions g(i) : X-i -&gt; A for i = 1, . . . , n, such that for every input x(1), . . . , x(n) the function g(x(1), . . . , x(n)) takes one of the values g(1)(x(1)), . . . , g(n)(x(n)). Given a discrete function g, it is an interesting problem to ask whether g is separable or not. Although this seems to be a very basic problem concerning discrete functions, the complexity of recognition of separable discrete functions of n variables is known only for n = 2. In this paper we will show that a slightly more general recognition problem, when g is not fully but only partially defined, is NP-complete for n &gt;= 3. We will then use this result to show that the recognition of fully defined separable discrete functions is NP-complete for n &gt;= 4. The general recognition problem contains the above mentioned special case for n = 2. This case is well-studied in the context of game theory, where (separable) discrete functions of n variables are referred to as (assignable) n-person game forms. There is a known sufficient condition for assignability (separability) of two-person game forms (discrete functions of two variables) called (weak) total tightness of a game form. This property can be tested in polynomial time, and can be easily generalized both to higher dimension and to partially defined functions. We will prove in this paper that weak total tightness implies separability for (partially defined) discrete functions of n variables for any n, thus generalizing the above result known for n = 2. Our proof is constructive. Using a graph-based discrete algorithm we show how for a given weakly totally tight (partially defined) discrete function g of n variables one can construct separating functions g(1), . . . , g(n) in polynomial time with respect to the size of the input function. (C) 2019 Elsevier B.V. All rights reserved.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA15-15511S" target="_blank" >GA15-15511S: Booleovské techniky v reprezentaci znalostí</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Discrete Mathematics

ISSN

0012-365X

e-ISSN

—

Svazek periodika

342

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

18

Strana od-do

1275-1292

Kód UT WoS článku

000462691000006

EID výsledku v databázi Scopus

2-s2.0-85060874537