Geodesic
About the potential for the ellipsoid method application to the threshold function recognition
Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 163-165.

Voir la notice de l'article provenant de la source Math-Net.Ru

For solving the decision problem about whether a Boolean function is threshold, the ellipsoid method is proposed to use. A polynomial complexity of the algorithm developed for this method by L. G. Khachiyan allows to expect that the computing complexity of the decision problem just mentioned is also polynomial.
Keywords: threshold function, ellipsoid method
Mots-clés : Khachiyan's algorithm. 
@article{PDMA_2017_10_a62,
     author = {I. I. Lapikov},
     title = {About the potential for the ellipsoid method application to the threshold function recognition},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {163--165},
     publisher = {mathdoc},
     number = {10},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2017_10_a62/}
}
TY  - JOUR
AU  - I. I. Lapikov
TI  - About the potential for the ellipsoid method application to the threshold function recognition
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2017
SP  - 163
EP  - 165
IS  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2017_10_a62/
LA  - ru
ID  - PDMA_2017_10_a62
ER  - 
%0 Journal Article
%A I. I. Lapikov
%T About the potential for the ellipsoid method application to the threshold function recognition
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2017
%P 163-165
%N 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2017_10_a62/
%G ru
%F PDMA_2017_10_a62
I. I. Lapikov. About the potential for the ellipsoid method application to the threshold function recognition. Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 163-165. http://geodesic.mathdoc.fr/item/PDMA_2017_10_a62/

[1] Khachiyan L. G., “Polinomialnye algoritmy v lineinom programmirovanii”, ZhVMiMF, 20:1 (1980), 51–68 | MR | Zbl

[2] Zuev A. Yu., “Porogovye funktsii i porogovye predstavleniya bulevykh funktsii”, Matematicheskie voprosy kibernetiki, 5, 1994, 5–61 | Zbl

[3] Nikonov V. G., “Porogovye predstavleniya bulevykh funktsii”, Obozrenie prikl. i promyshl. matematiki, 1:3 (1994), 458–545 | Zbl

[4] Kudryavtsev L. G., “Teoriya testovogo raspoznavaniya”, Diskretnaya matematika, 18:3 (2006), 3–34 | DOI | MR | Zbl

[5] Burdelev A. V., Nikonov V. G., Lapikov I. I., “Raspoznavanie parametrov uzla zaschity informatsii, realizovannogo porogovoi $k$-znachnoi funktsiei”, Trudy SPIIRAN, 46, 2016, 108–127

[6] Dertouzos P., Porogovaya logika, Mir, M., 1967, 344 pp.

[7] Lapikov I. I., Nikonov V. G., “Adaptivnyi algoritm resheniya sistem neravenstv s $k$-znachnymi neizvestnymi”, Trudy Voenno-kosmicheskoi akademii im. A. F. Mozhaiskogo, 2016, no. 1, 88–94