Ruby NoName Podcast S04E10
Podcast
http://ruby.rpod.ru/276289.html
news
- Libskypekit and Skypekit - C and Ruby interface for Skype
- Gem for working with Google spreadsheet
- PostgreSQL datatypes support in Rails 4
- Ruby 2.0 roadmap
- The Bastards Book of Ruby
- Continuos deployment for ruby gems
- Ruboto 0.6.0
- Mechanize 2.5
- Gem for asynchronously sending mail from devise - devise-async
- Chapter from Ruby Under a Microscope
- Last attempt to get on devConf
Discussion
NP completeness
- To get acquainted with the basic definitions and theorems, it is recommended to read the book: M. Gary, D. Johnson,
“Computing machines and difficult problems”. - Random_k-SAT
- [VV1986] LG Valiant, VV Vazirani, NP is as easy as detecting unique solutions (it is shown that search solutions to instances having a unique solutions, are as hard as SAT, under randomized reduction)
- [Var1982] M. Vardi, Complexity of Relational Query Languages
- [Imm1986] N. Immerman, Relational Queries Computable in Polynomial Time ([Imm1982] and [Var1982] give th. Immerman-Vardi that FO (LFP) = P)
- Wiki, which collects basic data on verification and paper
- Apparently the first or one of the first references to paper on the Internet
- First comment prof. Liption
- Links to rest there in the wiki, here's another important comment ,
which publishes an Liption Immerman, Deolalikar that unnecessarily uses only mondaic fixed points and
points out that it relies on a property in his proof, but points out that if he does not receive all the P. Thus,
it turns out that Deolalikar incorrectly applies the Immermana-Vardi theorem. Error found! - Other: mentioned “brick”: T. Cormen, C. Leiserson, R. Rivest, “Algorithms: construction and analysis”
Current
- Our competition is over, the results are summed up.
- Ivan Evtukhovich went to work in Express42 .