Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
On recognizing integer polyhedra - MaRDI portal

On recognizing integer polyhedra (Q2639642)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On recognizing integer polyhedra
scientific article

    Statements

    On recognizing integer polyhedra (English)
    0 references
    1990
    0 references
    Given a rational system Ax\(\leq b\) of linear inequalities, does it determine an integer polyhedron? In \textit{A. Schrijver} [Discrete Appl. Math. 14, 111-133 (1986; Zbl 0602.90111)] noted that this problem is in co-NP. He asked whether this problem is also in NP. In this note, the authors proved that the problem is co-NP complete. So, it is unlikely in NP.
    0 references
    rational system of linear inequalities
    0 references
    integer polyhedron
    0 references
    0 references

    Identifiers