The Systems Biology of COVID-19 and the SARS-CoV-2 virus. The class will build a foundation that includes the emergence of complexity, simple biological subsystems, their reductionist and equivalent toy and organ-chip models, and the measurements required to specify model architecture and parameters. Applications to biology, physiology, medicine, chemical and biological defense, pharmacology, drug discovery, and toxicology. UGrad: PHYS 240 01 and BME 290B; Grad: PHYS 326 and BME 395C.
Friday, January 23, 2015
SysBio15 Asgn_7B_Class_07_Short Presentation_02_2015_01_27
Computation: Review Short Presentation 02
Pino_SP-NP-complete_vs_np-hard_2015_01_20.pptx. in the
Student_Short_Presentations folder in the VU-Box and figure out as much
as you can on your own. Post a PCRC on the Blog, focusing on what you
want explained in more detail.
Subscribe to:
Post Comments (Atom)
Cameron Togrye
ReplyDeleteAssgn_7B / NP-Complete vs NP-Hard
0. Knew: I knew basically nothing related to this subject
1.Learned: There is a group of NP problems called NP-complete which form the hardest of the NP problems, and all of these NP-complete problems have the same core difficulty (sudoku is equivalent to protein folding)
2. What is the difference between a non-deterministic and a deterministic Turing Machine?
3. Presentation: Examples in Science of P, NP-complete, and NP-hard problems
4. My experience with this branch of computer science is fairly limited, so I would appreciate direct explanation from the presenter.
Kate Jones
ReplyDeleteAssignment 7B NP-Hard NP-Complete
0. Knew: I knew nothing about computational complexity besides the vast technological advances that allow us to do enormous calculations on handheld devices like cell phones.
1. Learned: Many of the difficult computational problems facing researchers today, such as understanding protein folding, relate to the same P vs NP debate on computational complexity. P problems can be solved in a certain number of steps (n^k) where increasing k indicates the computational complexity.
2. Pressing ?: A common example of an NP problem is solving a sudoku puzzle. It takes a while to solve, but checking the solution is fairly quick. If the difficulty of sudoku is the inherent complexity of the puzzle rather than the ability of the solver, how then are there 'sudoku solvers' online that can solve the puzzle instantaneously? Is it retrieving a saved puzzle rather than solving the puzzle?
3. Presentation: More elaboration on NP-Hard vs NP-Complete rather than P vs NP
4. I did not know that some problems that would seem to be fairly easily computable, such as the best move to make in a chess game, are actually quite complex and relate to a larger field of computational complexity.
Arman Chowdhury
ReplyDeleteAssignment 7B
Questions: What does it mean to verify a proof in NP problems, and how is it done? Can NP, NP-Complete and NP-Hard problems be reduced to P? What is the use of a Turing machine?
Juan Gnecco
ReplyDeleteAssignement 7B
Knew: Nothing about the difference in problems such as NP and N.
Learned: The (complicated) definition of N vs NP problem and how it can be applicable to defining parameters of disease.
Pressing: Can you elaborate on examples of N vs NP decision problems? Can biology be considered in a certain category? Seems too complex for a yes or no question. Is the computational power simply mathematical algorithms/computer coding?
Thoughts: Know very little about this field seems to me that NP problems in terms of biology is too complex to solve computationally if anything it fits into NP-hard or more complex (>polynomial problems)
Cami Johnson
ReplyDeleteAssignment 7B: NP-hard vs NP-complete
0. Knew: I knew nothing about any of this.
1. Learned: P is classification of problem which can be solved computationally. NP is a classification of problem which can be verified computationally, but not solved. NP-complete is a classification of problem which can be computationally reduced to another NP problem.
2. Pressing ?: Are NP-hard problems basically just ones which don't fit into the other three categories? Can NP problems be solved computationally, but it just takes much longer than P problems?
3. Presentation: examples of NP-complete and NP-hard problems in biology
4. Thoughts: Because I know so little about this subject, I'm still a little unclear on some of the distinctions. I think some more explanation and examples in class will help me understand better.
Tim Lee
ReplyDeleteAsgn_7B
Questions:
I don't quite get the criteria of what a NP-hard is. How do you classify how hard a problem is and how do you compare difficulty across problems? I would love to know more about the Turing machine.
Priyanka Ravichandran
ReplyDeleteAssignment 7B
0. Knew - I did not know about this topic
1. Learned - the different classes of problems
2. Pressing - I would like the examples mentioned in the PPT to be explained a bit further. Also, how does this relate to systems biology?
Mark Vander Roest
ReplyDeleteAssignment 7B
0. Knew: I saw a few words in there that I recognized but not much else. I knew that modeling from first principles is a goal, but had no clue of the current work towards it.
1. Learned: P, NP, NP-complete, and NP-Hard definitions and how they apply to the challenge of solving complex problems with ever increasing computational power.
2. Pressing ?: What are the current predictions for solving such complex problems following Moore's law and the inevitable plateau it hits?
3. Presentation: The concepts of NP-Complete/hard problems.
4. Thoughts: Cool stuff, but definitely way over my head.
Shuaipeng "Jimmy" Zhang
ReplyDeleteAssignment 7B
0. Knew: Not much in the presentation.
1. Learned: Classification of problems: P, NP, NP-complete, NP-hard.
2. Pressing ?: How does a Turing machine go about solving NP problems? What other criteria can be used to classify NP-hard problems other than just "being harder"?
3. Presentation: Differences between NP-hard and NP-complete problems, some examples?
4. Thoughts: I learned some definitions in this presentation, but really don't grasp the concept of NP-complete/NP-hard problems.
Zach Bednarke
ReplyDeleteAsgn 7b
Knew: the concept of polynomial time
Learned: the "P vs NP" problem is just the tip of the iceberg. Delving into NP Hard and NP complete seems incredibly difficult.
Pressing ?: Godel's incompleteness theorem states that mathematics is incomplete. Are the problems unanswerable by math NP-Hard or worse?
Presentation: Comparing today's challenge of "P vs NP" to "NP Hard vs NP Complete"
Thoughts: Modeling cells from first principles is a problem that I think must be NP Hard. But we can approximate solutions- systems biology is attacking this NP Hard problem and we hope to come close to a set of "solutions" that will suffice for our needs. Can other NP Hard problems be tackled in this way?
Chuck Herring
ReplyDelete7b
Questions: Has anyone claimed to have solved P=NP?
Selene van der Walt
ReplyDeleteAssignment 7B
0. Knew: I knew basically nothing about this subject before looking at this presentation.
1. Learned: The distinction between P and NP problems, and that problems are easier to solve if you can quickly solve a similar problem.
2. Pressing?: What exactly is polynomial time? Why do any of these distinctions matter?
3. Presentation: NP hard and NP complete and how it refers to problem solving capabilities in systems modeling.
4. Thoughts: This seems interesting but I think I do not grasp the concept well enough to fully understand the implications.