Are There Any Problems That Cannot Be Solved in Linear Time?

  • Thread starter Thread starter Dragonfall
  • Start date Start date
AI Thread Summary
The discussion centers on identifying problems that are suspected of not having linear-time solutions, highlighting examples such as multiplication, sorting, and various NP-complete problems like factoring and the traveling salesman problem. Participants mention poly-time problems, including the Fast Fourier Transform and calculating trigonometric functions to a specified precision. Other examples include finding the first "n" primes and defragmenting a disk with "n" fragments. The conversation also touches on the theoretical aspect of counting to "n," which could require increasingly longer word lengths. Overall, the thread explores the complexities of algorithm efficiency and problem classification in computational theory.
Dragonfall
Messages
1,023
Reaction score
5
Can I have a list of problems suspected of not having linear-time solutions? Like multiplication and sorting.
 
Mathematics news on Phys.org
I meant a poly-time problem.
 
Fast Fourier transform (2d or 3d).
Most trigonometric functions to any specified precision.
Finding the first "n" primes.
Defragmenting a disk with "n" fragments.

Technically, counting to "n" because eventually you would need longer and longer word-lengths.
 

Thread 'Non-orthogonal bases'

Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
View full post »

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
View full post »

Similar threads

B A symmetric problem has an asymmetric solution - why?
Replies
21
Views
2K
I How do you solve systems of equations in complex physics problems?
Replies
6
Views
2K
I Relevant Literature for Noisy Linear Dynamical Systems
Replies
1
Views
2K
I The Price of Beer - Linear Algebra Problem
Replies
44
Views
5K
MHB Communication in mathematics and physics
Replies
1
Views
2K
A How to use the Newton-Raphson method while keeping the sum constant?
Replies
2
Views
2K
B Are Inverse Problems More Complex Than Direct Problems in Mathematics?
Replies
13
Views
3K
B Can Multiple Outputs from a Single Input Help in Constructing Non-Linear Curves?
Replies
7
Views
2K
B Can Linear Systems of Equations Have More Than Three Solutions?
Replies
29
Views
3K
I Area divided by linear function
Replies
8
Views
2K

Hot Threads

Recent Insights

Back
Top