Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Border basis detection is NP-complete   Border basis detection (BBD) is described as follows: given a set of
generators of an ideal, decide whether that set of generators is a border basis
of the ideal with respect to some order ideal. The motivation for this problem
comes from a similar problem related to Gr\"obner bases termed as Gr\"obner
basis detection (GBD) which was proposed by Gritzmann and Sturmfels (1993). GBD
was shown to be NP-hard by Sturmfels and Wiegelmann (1996). In this paper, we
investigate the computational complexity of BBD and show that it is
NP-complete.

23
The categories of this paper are: solv-int
31
The categories of this paper are: ao-sci
32
The categories of this paper are: atom-ph
29
The categories of this paper are: funct-an
37
The categories of this paper are: supr-con
36
The categories of this paper are: cmp-lg
20
The categories of this paper are: acc-phys
7
The categories of this paper are: hep-th
13
The categories of this paper are: quant-ph
17
The categories of this paper are: q-fin
3
The categories of this paper are: physics
9
The categories of this paper are: nlin
11
The categories of this paper are: hep-lat
4
The categories of this paper are: cond-mat
10
The categories of this paper are: q-bio
28
The categories of this paper are: alg-geom