NL完全

在计算复杂性理论中，NL完全是由全体对NL类完备的语言构成的复杂性类。也就是说，NL完全的语言是NL类中最“难解”和最“有力”的语言。如果有某个确定性的方法可以在对数空间内解决一个NL完全问题，那么就会有NL=L。NL完全是由全体对NL类完备的语言构成的复杂性类。也就是说，NL完全的语言是NL类中最“难解”和最“有力”的语言。如果有某个确定性的方法可以在对数空间内解决一个NL完全问题，那么就会有NL=L。