如何证明语言属于P类或未知？L1与L2的判定证明求助

关于L₁ = { | G是包含n-5团的图 } #

L₁属于P类，证明如下：

• 核心逻辑：原图G存在n-5团，等价于存在一个大小为5的顶点子集T，使得G中去掉T后的剩余顶点集V\T是一个团（即V\T中任意两个顶点之间都有边）。
• 算法设计：
  1. 枚举图G中所有可能的5顶点子集T，总数量为组合数C(n,5)，时间复杂度为O(n⁵)（多项式级别）。
  2. 对每个子集T，检查V\T中的所有顶点是否两两相连：遍历V\T中所有顶点对，判断边是否存在，时间复杂度为O((n-5)²) = O(n²)。
• 整体时间复杂度：O(n⁵ × n²) = O(n⁷)，属于多项式时间，因此该语言可被多项式时间算法判定，故L₁∈P。

关于L₂ = { | G是包含欧拉路径的图 } #

L₂属于P类，并非状态未知，证明如下：

• 欧拉路径的判定定理：
  • 无向图场景：图连通，且恰好有0个（对应欧拉回路）或2个顶点的度数为奇数。
  • 有向图场景：图弱连通，且恰好存在一个顶点出度比入度多1、一个顶点入度比出度多1，其余顶点入度等于出度；或所有顶点的入度与出度相等（对应欧拉回路）。
• 算法设计：
  1. 检查图的连通性（无向图用DFS/BFS，有向图检查弱连通），时间复杂度O(V+E)。
  2. 统计每个顶点的度数（无向图）或入度/出度（有向图），时间复杂度O(V+E)。
  3. 根据上述定理验证度数条件，时间复杂度O(V)。
• 整体时间复杂度为O(V+E)，属于多项式时间，因此L₂∈P。

内容的提问来源于stack exchange，提问作者Martian_mars