Meta-complexity investigates the complexity of computational problems and tasks that are themselves about computations and their complexity. Understanding whether such problems can capture the hardness of NP is a central research direction. A longstanding open problem in this area is to establish the NP-hardness of MINKT (Ker-I Ko, 1991 [Ker{-}I Ko, 1991]), the problem of estimating time-bounded Kolmogorov complexity. We contribute to this research direction by studying nK^t, a natural variant of Kolmogorov complexity that captures the complexity of representing a string using time-bounded nondeterministic computations [Buhrman et al., 2001]. Let MINnKT denote the task of estimating nK^t(x) of a given input string x. We prove that MINnKT ∈ BPP if and only if NP ⊆ BPP. This can be interpreted as a solution to Ko’s question in the setting of nondeterministic time-bounded Kolmogorov complexity. Crucial to the proof of this result is the investigation of a new notion of probabilistic nondeterministic time-bounded Kolmogorov complexity called pnK^t. This measure can be seen as an extension of pK^t complexity [Halley Goldberg et al., 2022] obtained by replacing 𝖪^t with nK^t. We establish unconditionally that pnK^t has nearly all key properties of (time-unbounded) Kolmogorov complexity, such as language compression, conditional coding, and a form of symmetry of information. Finally, we show that the corresponding meta-computational problem MINpnKT also captures the hardness of NP, and that extending this result to the closely related problem Gap-MINpnKT would imply the exclusion of PH-Heuristica.

Symmetry of Information (SoI) is a fundamental result in Kolmogorov complexity stating that for all n-bit strings x and y, we have K(x,y) = K(y) + K(x ∣ y) up to an additive error of O(logn). In contrast, understanding whether SoI holds for time-bounded Kolmogorov complexity measures is closely related to longstanding open problems in complexity theory and cryptography, such as the P versus NP question and the existence of one-way functions.

Software Defined Networking (SDN) decouples the control plane from the data plane, which increases network scalability and flexibility. But malicious applications on SDN controller can cause the entire network to crash. So, we design a reputation and incentive mechanism on SDN to reduce application's malicious access. In the proposed module, first of all, the application behavior is analyzed and the malicious accesses are identified, which are used to build the reputation and incentive mechanism. Second, the analysis results of the application behavior are combined through beta probability density to obtain the reputation rating. The reward or punishment will be given based on the behavior and reputation of the application under the selected social strategy. Simulation results show that the system can accurately identify malicious behavior and reduce malicious requests, with an acceptable runtime overhead about 300 microseconds.