The Complexity of Local Dimensions for Constructible Sets
The Complexity of Local Dimensions for Constructible Sets
复制标题
可构造集局部维度的复杂性
作者：
P. Koiran
我们表明，决定一个代数簇是否有一个不可约组件的余维至少d是一个NPC-完全的问题，为每一个固定的d（是在阿瑟-梅林类，如果我们假设一个位模型的计算）。然而，当d不是固定的，而是输入的一部分，我们表明，这个问题是不可能在NPC或coNPC。这些结果被推广到任意的可构造集。我们还研究了其他一些相关问题的复杂性。
We show that deciding whether an algebraic variety has an irreducible component of codimension at least d is an NPC-complete problem for every fixed d (and is in the Arthur–Merlin class if we assume a bit model of computation). However, when d is not fixed but is instead part of the input, we show that the problem is not likely to be in NPC or in coNPC. These results are generalized to arbitrary constructible sets. We also study the complexity of a few other related problems.