An upper bound for the maximum cut mean value (Q4373671)

Exact solution of any NP-hard problem requires performance of tests whose number is exponentially dependent on the problem size. Therefore, solving NP-hard problems by inspection, i.e. performing the requested number of tests, is possible only for limited size instances of the problem. Nevertheless, numerous solutions exist if the structure of a given instance of the NP-hard problem is ``dense''. Then, random selection of substructures and test them for a solution enables us to solve the problem expecting the number of requested tests that is estimated by a polynomial on size of the instance. The paper supplies the proof that expectations \(f(x,n)\) and \(r(x,n)\) for sufficiently large \(x\): \[ \lim_{n\to \infty} f(x,n) \leq {1\over 2} +\sqrt {{\ln 2\over 2x}}, \quad \lim_{n\to\infty} r(x,n) \leq {1\over 2} +{1\over \sqrt x} +{1\over 2} {\ln 2 \over x}, \] where \(f(x,n)\) denotes the expectation of a subset of vertices, \(r(x,n)\) denotes the corresponding expectation for random \(2x\)-regular graphs, \(n\) is the number of graph vertices, and \(x\) is the number of graph edges, are the solution of the MAXIMUM CUT problem for a random graph. Similar results were investigated earlier for the MAXIMUM CLIQUE problem. The basic idea of the given proofs is the estimation of the number of given type submatrices included in the adjacency matrix of fixed size that represents a random graph. In order to make the extension of these results on a wide class of NP-hard problems concerning different structures it is worthwile to mention that numerous historically investigated NP-hard problems can be seen as instances of intractable matrix problems, see \textit{A. Kapralski} [Sequential and parallel processing in depth search machines (1994; Zbl 0840.68031)]. Solving any such NP-hard problem means finding a specific submatrix. Then, in order to complete the concerned proofs, we have to estimate the number of specific submatrices or sets of such submatrices included in a random matrix that represents a given structure. For the entire collection see [Zbl 0877.00011].