Loading...
(function(){<br />
let canvas = document.createElement('canvas'),<br />
ctx = canvas.getContext('2d'),<br />
w = canvas.width = innerWidth,<br />
h = canvas.height = innerHeight,<br />
particles = [],<br />
properties = {<br />
bgColor : 'rgba(17, 17, 19, 1)',<br />
particleColor : 'rgba(255, 40, 40, 1)',<br />
particleRadius : 3,<br />
particleCount : 60,<br />
particleMaxVelocity : 0.5,<br />
lineLength : 150,<br />
particleLife : 6,<br />
};<br />
<br />
document.querySelector('body').appendChild(canvas);<br />
<br />
window.onresize = function() {<br />
w = canvas.width = innerWidth;<br />
h = canvas.height = innerHeight;<br />
}<br />
<br />
class Particle {<br />
constructor() {<br />
this.x = Math.random()*w;<br />Loading...
This is a short summary of the section on problem classes in the book Computer Science Guide by William Springer.
Classification of problems based on the time required to solve them, depending on the size of the input data. This classification helps determine the computational complexity of problems.
The P complexity class contains the simplest computational problems—those that can be solved in polynomial time. In other words, the time required to solve the problem grows as the size of the input raised to some fixed constant power, such as O(n), O(n²), or O(n³).
A classic example is sorting a list, which can be performed by efficient algorithms such as Merge Sort or Heap Sort in O(n log n) time.
The P class is a proper subset of the EXP (Exponential Time) class, which contains problems solvable in exponential time. Every problem that can be solved in polynomial time can also be solved in exponential time—for example, any algorithm with complexity O(n²) is also bounded by O(2ⁿ) for sufficiently large n. However, exponential-time algorithms become impractical much more quickly as the input size increases.
The NP complexity class consists of problems whose solutions can be verified in polynomial time by a deterministic algorithm. Like P, the NP class is a subset of EXP (Exponential Time).
The term nondeterministic refers to a theoretical computational model in which an algorithm can always make the "correct" choice whenever multiple possibilities exist. Unlike a deterministic algorithm, which follows the same sequence of steps for a given input and always produces the same result, a nondeterministic algorithm may conceptually explore many possible execution paths simultaneously.
In other words, there exists a hypothetical algorithm that solves an NP problem by making a sequence of choices, always selecting the correct option at each decision point. While such an algorithm is not physically realizable, it provides a useful theoretical framework for classifying computational problems. Importantly, once a candidate solution is found, its correctness can be verified by a deterministic algorithm in polynomial time.
The NP class is a superset of P. Every problem that can be solved in polynomial time can also have its solution verified in polynomial time. However, one of the most important open questions in computer science is the P versus NP problem: Is P equal to NP, or is P a proper subset of NP? Despite decades of research, this question remains unsolved.
An NP-hard problem is, informally, at least as difficult as the hardest problems in NP. More formally, a problem is NP-hard if every problem in NP can be reduced to it in polynomial time. This means that if we had an efficient algorithm (or an oracle) for solving an NP-hard problem, we could use it to solve every problem in NP efficiently. An NP-hard problem does not have to belong to NP—for example, it may not even be a decision problem.
A problem that is both NP-hard and a member of NP is called NP-complete. These are the hardest problems within NP, and they play a central role in computational complexity theory.
If an NP-complete problem admits a pseudo-polynomial-time algorithm, it is called weakly NP-complete. Otherwise, it is considered strongly NP-complete (assuming P ≠ NP).
Many other complexity classes are defined using variations of the Turing machine model, which serves as the standard theoretical foundation for computational complexity.