李晓杰暖心力作《早点回家》MV上线 缩短春运回家路

百度 国土资源部要求,县级以上国土资源主管部门要强化土地执法监察,及时发现、制止和严肃查处违法乱占耕地特别是永久基本农田的行为,对违法违规占用永久基本农田建窑、建房、建坟、挖砂、采石、取土、堆放固体废弃物或者从事其他活动破坏永久基本农田,毁坏种植条件的,要及时责令限期改正或治理,恢复原种植条件,并按有关法律法规进行处罚,构成犯罪的,依法追究刑事责任；对破坏或擅自改变永久基本农田保护区标志的,要及时责令限期恢复原状。

In complexity theory, UP (unambiguous non-deterministic polynomial-time) is the complexity class of decision problems solvable in polynomial time on an unambiguous Turing machine with at most one accepting path for each input. UP contains P and is contained in NP.

A common reformulation of NP states that a language is in NP if and only if a given answer can be verified by a deterministic machine in polynomial time. Similarly, a language is in UP if a given answer can be verified in polynomial time, and the verifier machine only accepts at most one answer for each problem instance. More formally, a language L belongs to UP if there exists a two-input polynomial-time algorithm A and a constant c such that

if x in L , then there exists a unique certificate y with $|y|=O(|x|^{c})$ such that ?$A(x,y)=1$?

if x is not in L, there is no certificate y with $|y|=O(|x|^{c})$ such that ?$A(x,y)=1$?

algorithm A verifies L in polynomial time.

UP (and its complement co-UP) contain both the integer factorization problem and parity game problem. Because determined effort has yet to find a polynomial-time solution to any of these problems, it is suspected to be difficult to show P=UP, or even P=(UP ∩ co-UP).

The Valiant–Vazirani theorem states that NP is contained in RP^Promise-UP, which means that there is a randomized reduction from any problem in NP to a problem in Promise-UP.

UP is not known to have any complete problems.

References

Sources

• Hemaspaandra, Lane A.; Rothe, J?rg (June 1997). "Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets". SIAM Journal on Computing. 26 (3): 634–653. arXiv:cs/9907033. doi:10.1137/S0097539794261970. ISSN 0097-5397.