The proof-complexity tag has no wiki summary.
-1
votes
0answers
31 views
In a directed graph, the indegree of a node is the number of incoming edges and the outdegree is the number of outgoing edges [duplicate]
In a directed graph, the indegree of a node is the number of incoming edges and
the outdegree is the number of outgoing edges. Show that the following problem
is NP-complete. Given an undirected graph ...
3
votes
2answers
71 views
Lower bound on size of proof that a list of integers is sorted
Suppose we have a list of unbounded integers, written in binary, and we want to write a (formal) proof that the list is sorted in ascending order.
Such a proof might look (informally) like: "2 < ...
