10 (Free) Data Structure and Algorithm Courses for Computer Science Students and Junior developers Computer Science

---

• 10 (Free) Data Structure and Algorithm Courses for Computer Science Students and Junior developers
• Google AI ‘EfficientNets’ Improve CNN Scaling
• Details and link for a proof of P = NP

10 (Free) Data Structure and Algorithm Courses for Computer Science Students and Junior developers Posted: 05 Jun 2019 07:33 AM PDT submitted by /u/javinpaul [link] [comments]

Google AI ‘EfficientNets’ Improve CNN Scaling Posted: 05 Jun 2019 09:16 AM PDT submitted by /u/Yuqing7 [link] [comments]

Details and link for a proof of P = NP Posted: 05 Jun 2019 05:23 PM PDT I have proved the $P$ versus $NP$ showing that we can polynomially reduce a known $\textit{NP—complete}$ problem $\textit{MONOTONE 1–IN–3 3SAT}$ into the polynomial language $\textit{2SET PACKING}$. If any $\textit{NP--complete}$ problem can be solved in polynomial time, then every language in $NP$ has a polynomial time algorithm. In conclusion, we finally prove that $P = NP$. Here are the arguments of the proof (you can download the details in The P versus NP Problem): "I have a polynomial algorithm for $\textit{MONOTONE 1–IN–3 3SAT}$ that no one has found before: The trick is that I noticed given an instance $\phi$ of the language $\textit{MONOTONE 1–IN–3 3SAT}$, then we can construct a Boolean formula $\phi'$ in $CNF$ such that — If $\phi'$ has a truth assignment with exactly one true literal for each clause, then $\phi$ complies with the same property. — $\phi'$ contains the clauses of $\phi$ but modified and there are at most two clauses of two literals for each occurrence of a literal from every clause in $\phi$. In this way, there are at most polynomially number of clauses in $\phi'$ in relation to $\phi$. — We replace each occurrence of any variable into a single clause in $\phi$ by some unique variable in $\phi'$ which appears in $\phi'$ as follows: Once negated in a clause of two literals and twice as a positive literal in a clause of two and three literals when the variable occurrences appear more than once in $\phi$. We create sets of fewer than three elements assigned to each literal from every clause into $\phi'$, such that the set assigned to the negated literal of some variable is not mutually disjoint with the sets assigned to the two positive literals from this unique variable in $\phi'$. Moreover, we modify those sets with exactly two elements just adding a common element to the sets of the literals of every clause in $\phi'$, because this guarantee that the sets assigned to the literals of each clause are not mutually disjoint. The amount of sets in this procedure is small since there are exactly the same amount of sets which is equal to the total number of literals for each clause in $\phi'$. In this way, a truth assignment $T$ for the Boolean formula $\phi'$ of $m'$ clauses with exactly one true literal for each clause corresponds to $m'$ mutually disjoint sets assigned for the literals that were true in this assignment, that is the negated or positive literal when the variable in $T$ is false or true respectively. Certainly, the possibility between $m'$ mutually disjoint sets when every clause of two literals has exactly one set chosen from its literals makes possible the appropriated assignment of all the variables in $\phi$ where they were replaced by several unique variables in $\phi'$ when we evaluate as true each literal which has been assigned from every selected set. At the same time, we obtain the property between $m'$ mutually disjoint sets when every clause of three literals has exactly one set chosen from its literals converts this into a certificate for the clauses of three literals in $\phi$ which are equivalent to the modified clauses of three literals that contain $\phi'$ when we evaluate as true each literal which has been assigned from every selected set. In this way, the collection of these sets is an instance of the polynomial language $\textit{2SET PACKING}$ assuming that we require $m'$ mutually disjoint sets. If we cannot pick $m'$ mutually disjoint sets from this collection, then this will imply $\phi'$ has not a truth assignment with exactly one true literal for each clause. The reason is because if we cannot choose a single set for every clause, then there is not a truth assignment where we may select as true exactly one literal for each clause in $\phi'$. In addition, we cannot obtain $m'$ mutually disjoint sets where there is a literal and its negation within the selected sets since as we explained above those assigned sets are not mutually disjoint." submitted by /u/frankvegadelgado [link] [comments]

You are subscribed to email updates from Computer Science: Theory and Application. To stop receiving these emails, you may unsubscribe now.	Email delivery powered by Google
Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States