اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTowards a Resolution of P = NP Conjecture
87
0
0.0
(
0
)
تأليف
Garimella Rama Murthy
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this research paper, the problem of optimization of a quadratic form over the convex hull generated by the corners of hypercube is attempted and solved. It is reasoned that under some conditions, the optimum occurs at the corners of hypercube. Results related to the computation of global optimum stable state (an NP hard problem) are discussed. An algorithm is proposed. It is hoped that the results shed light on resolving the P not equal to NP problem.
قيم البحث
اقرأ أيضاً
We prove the cohomological crepant resolution conjecture of Ruan for the weighted projective space P(1,3,4,4). To compute the quantum corrected cohomology ring we combine the results of Coates-Corti-Iritani-Tseng on P(1,1,1,3) and our previous results.
Mustac{t}u{a} has given a conjecture for the graded Betti numbers in the minimal free resolution of the ideal of a general set of points on an irreducible projective algebraic variety. For surfaces in $mathbb P^3$ this conjecture has been proven for
points on quadric surfaces and on general cubic surfaces. In the latter case, Gorenstein liaison was the main tool. Here we prove the conjecture for general quartic surfaces. Gorenstein liaison continues to be a central tool, but to prove the existence of our links we make use of certain dimension computations. We also discuss the higher degree case, but now the dimension count does not force the existence of our links.
We consider three graphs, $G_{7,3}$, $G_{7,4}$, and $G_{7,6}$, related to Kellers conjecture in dimension 7. The conjecture is false for this dimension if and only if at least one of the graphs contains a clique of size $2^7 = 128$. We present an aut
omated method to solve this conjecture by encoding the existence of such a clique as a propositional formula. We apply satisfiability solving combined with symmetry-breaking techniques to determine that no such clique exists. This result implies that every unit cube tiling of $mathbb{R}^7$ contains a facesharing pair of cubes. Since a faceshare-free unit cube tiling of $mathbb{R}^8$ exists (which we also verify), this completely resolves Kellers conjecture.
The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta t
heorem give a strong characterization of such functions whenever the bound on the total influence is $o(log n)$. However, both results become useless when the total influence of the function is $omega(log n)$. The only case in which this logarithmic barrier has been broken for an interesting class of functions was proved by Bourgain and Kalai, who focused on functions that are symmetric under large enough subgroups of $S_n$. In this paper, we build and improve on the techniques of the Bourgain-Kalai paper and establish new concentration results on the Fourier spectrum of Boolean functions with small total influence. Our results include: 1. A quantitative improvement of the Bourgain--Kalai result regarding the total influence of functions that are transitively symmetric. 2. A slightly weaker version of the Fourier--Entropy Conjecture of Friedgut and Kalai. This weaker version implies in particular that the Fourier spectrum of a constant variance, Boolean function $f$ is concentrated on $2^{O(I[f]log I[f])}$ characters, improving an earlier result of Friedgut. Removing the $log I[f]$ factor would essentially resolve the Fourier--Entropy Conjecture, as well as settle a conjecture of Mansour regarding the Fourier spectrum of polynomial size DNF formulas. Our concentration result has new implications in learning theory: it implies that the class of functions whose total influence is at most $K$ is agnostically learnable in time $2^{O(Klog K)}$, using membership queries.
In this paper, we explore the suitability of upcoming novel computing technologies, in particular adiabatic annealing based quantum computers, to solve fluid dynamics problems that form a critical component of several science and engineering applicat
ions. We start with simple flows with well-studied flow properties, and provide a framework to convert such systems to a form amenable for deployment on such quantum annealers. We analyze the solutions obtained both qualitatively and quantitatively as well as the sensitivities of the various solution selection schemes on the obtained solution.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
