Complexity Definition and 148 Threads

Recent contents View information Top users
  1. S

    What is the meaning of M(n) in algorithm complexity analysis?

    I'm trying to teach myself some algorithm complexity and I've run into a problem. I'm starting to understand about O and o notation and big theta notation. I've run into notations like O(n^2 M(n)). Does this mean that the complexity is n^2 times whatever M(n) means? (Natural next question) what...
  2. N

    Complexity theory {Hamiltonian, DHC, IND}

    Hello, I need help with a couple of questions. (The answers haven't come up properly and are too cryptic and I'm having some difficulty). I'm trying really hard to learn this, so could you explain it as fully and clearly as possible - that would be of great help. (I find there are some...
  3. R

    Integrating Complexity: Solving \int \frac{1}{x^n(1+x^n)^{1/n}} \;\mathrm{d}x}

    Homework Statement An Integral : \int \frac{1}{x^n(1+x^n)^{1/n}} \;\mathrm{d}x} Homework Equations The Standard integrals. The Attempt at a Solution I'm aware that integrals like this become very easy after a clever substitution...but maybe I'm not that clever...
  4. K

    Energy and computational complexity of atomic interactions

    Hi Recently I've been pondering the causes of enormous difference in energy requirements between modeling a complex process like fluid dynamics on computer and the actual energy required in the physical fluid. In a computer, it takes hundreds or thousands of processors long periods of time to...
  5. inflector

    Complexity, The Standard Model and Higgs

    I've been reading most of the threads here in particle physics forum. Recently, I noted a couple of threads started by enotstrebor which were a bit impolitic. Nevertheless, they raised some issues which are similar to those I have myself with the Standard Model as well Quantum Mechanics in...
  6. R

    To which complexity class does this optimization problem belong?

    I'll try to be as abstract as possible, but where needed, I'll give some concrete examples. If you have any questions, please ask. Note, I'm doing this for my hobby, not for any sort of homework. I've only followed an introductory course on computational complexity, so I'll let that be my...
  7. T

    What Is the Statement Count for This Nested For-Loop?

    Homework Statement Find the statement count (not the worst-case scenario) of the following for-loop. for (int k = 0; k < N; k += 1) { for (int m = 0; m < k; m += 1) { sum = sum + values[k][m]; } for (int p = k; p < N; p += 1) { sum = sum +...
  8. H

    The Complexity of Simplicity: Expressing 1+1=2

    How to express 1+1=2 the most complicated way imaginable?
  9. N

    Understanding the Time Complexity of Nested Loops in Algorithms

    Ok, I am brand new at this so I am kind of confused how to figure this out. i \leftarrow n while i >= 1 j \leftarrow i while j <= n <body of the j loop>, needs (1) j \leftarrowj*2 end j while i \leftarrowi-1 end i while I know that with nested...
  10. D

    How is computational complexity determined?

    like for any algorithm? On wikipedia it lists for multiplication it's O(n^2) but some of them have decimals like O(5/2n^2.2342) or something so how would you determine that? Just use a computer and make a graph of input in bytes vs time in seconds and fit a curve to it? Like I understand for...
  11. D

    Complexity Classes as Pure Sets

    What are complexity classes (P, NP, etc) in terms of pure sets? ZFC, I mean.
  12. N

    Integrating Complexity: Indefinite Integral of e^(4x+(e^4x))

    Homework Statement Indefinite integral: e^(4x+(e^4x)) Homework Equations I'm thinking integration by parts, involving UV minus integral of Vdu The Attempt at a Solution So I saw that this can be split into two: e^(4x) times e^(e^4x)). The latter is a bit complicated. I...
  13. G

    Methods and complexity for computing square roots

    Hello everybody, Let's say we want to compute sqrt(x), where x is an integer of n digits. Then what is the cost of the computation, in terms of big O notation and n? And a second question: what is the algorithm for finding the square root that is most commonly used in computers and...
  14. F

    Algorithmic Complexity and Big-Oh notation

    Hi Guys, Is algorithmic complexity determined mostly for primality tests or on-to prime-generating functions? Say, I have the function, Floor[(n!)/(n+1)], and for every n it produces primes, would I have to use the trig definition of the floor function to determine the complexity of this...
  15. O

    Complexity Economics: What is it & How Has it Emerged?

    What is Complexity Economics? How has it emerged? This description sounds very interesting in Wikipedia: "It is one of the four C's of a new paradigm surfacing in the field of economics. The four C's are complexity, chaos, catastrophe and cybernetics." These four Cs sound so physical like...
  16. S

    How Does Runtime Affect the Kolmogorov Complexity of a SAT Solver's Output?

    I'm not entirely clear on the concept of kolmogorov complexity. Does it mean that the a certain string is complex if there is no combinatorial (not sequential) circuit which outputs that string or does it mean that a certain string is complex if there is no program which can output that string...
  17. M

    Insect Wings: Modeling the Complexity of Flight

    Hi everyone! I have a question for you :) I am wondering, if there already is a developed model, imitating insect wings, e.g. bee wings. If you happen to observe them, they seem to be much more complex, but also much more useful and allow a more flexible movement. Insects fly with them not...
  18. H

    Complexity of divide and conquer algorithm?

    Let's say I have some algorithm with complexity O(n^k) for some constant k. and let's say it runs in some time T. Now, I want to implement a divide and conquer approach for this algorithm, by dividing the problem in half each recursion. So basically, the first time i run my algorithm it will run...
  19. C

    Probabilistic complexity classes and acceptable sources of entropy

    (This may be a little bit outside the normal scope of this particular forum. I realized after writing this I didn't really know where to go with questions about computational complexity. Does anyone have any recommendations as to places where this question might be more appropriate? Anyway:)...
  20. D

    Complexity Class: O(f) Where f:N->N

    Besides being a partially ordered set by set inclusion, what else is the set of all classes O(f) where f:N->N.
  21. Cincinnatus

    I'm sure there are lots of way to define complexity in different

    I'm sure there are lots of way to define complexity in different contexts. Some that I've heard of include: -Minimum description length / Kolmogorov complexity -time complexity - number of steps to compute -parameter complexity - number of parameters needed to specify a model. There are...
  22. C

    How to find computational complexity?

    If i have a program, how can i find the computational complexity? is there some other program i can run in the background?
  23. C

    How Do You Manage Life's Complexities?

    hi I just wondered if anyone has a sound set of methodologies they apply in their daily life that helps them effectively deal with complexity in life. I feel for every person this set of principles would be different because of they way they are and the way their enviornment is. But perhaps...
  24. D

    The Twin Paradox: Exploring Its Complexity

    The twin paradox is very confusing, and even after reading the explanation, I still get questions. The only explanation of the paradox is when an object is first moving away from earth, and then moving towards the earth. They make it very complicated. How about just moving one direction, and...
  25. moe darklight

    Increasing/decreasing complexity (just a weird theory)

    It seems to be a law of nature that all things consist of smaller, less complex things: fundamental particles are (comparatively) simple. They react to form atoms, atoms form molecules, molecules form different chemicals, these chemicals also reach with each other to form cells, minerals, etc...
  26. C

    What is the lowest known complexity for multiplication?

    'Schoolbook' multiplication takes O(n^2) operations. Karatsuba multiplication takes O(n^{\lg 3})\approx O(n^{1.59}) operations. The best method I know of (which is only practical for very large numbers) is O(n \log n \log\log n). Is there a known nontrivial lower bound on the complexity of...
  27. G

    Prime Factorization Time Complexity

    While I know the time complexity for all known prime factorization algorithms is exponential, I can't seem to get this results for a very simple algorithm. First assume we're doing this with numbers that are simply the product of two primes (the kind you get when working with RSA and others)...
  28. H

    LaTeX Calculating Complexity with Big-O Notation

    \frac{<N!>}{<(N-n)!>} = <N^n> (1 + \mathcal{O}( \frac{1}{<N!>} )) The popup you get from clicking on this is missing lots of the code. I presume because my browser is trying to render things as HTML tags.
  29. D

    Algorithmic complexity of primes

    Every number can be considered a bit string. For a bit string one can define some algorithmic complexity (the shortest algorithm/program that reproduces the desired bit string). Can something be said, in general, about difference in complexity for primes as compared to composites?
  30. R

    What is the relationship between reductionism and complexity?

    I'm looking for some good definitions/ explanations of the two words reductionism and complexity. As I once read reductionist say emergent properties and complex behaviour are epistemological issues, necessary conceptualisations to make the world understandable. Any additional non-physical...
  31. N

    Space Complexity of Number-theoretic Algorithms

    Can you write an example where a space complexity of any number-theoretic algorithm is calculated? Thanks In Advance.
  32. S

    News Exploring Reality: Examining Complexity Beyond Idealism

    Hey Merc. Can you further explain exactly what you mean by that?
  33. I

    Complexity: distinctions of synonyms of original

    Complexity: distinctions of synonyms of "original" Assume everything (not as a single set but individually or a subsets of the universe) can be derived from something else. T or F ? Assume this is true (T). The word original is defined as : If such is the case with all things that...
  34. G

    Evolution of Complexity: Can Organisms Develop Immunity to Drugs Over Time?

    Do you think that given time, organisms become more and more complex no matter how slow the evolution of complexity is, organisms do get more complex over time?
  35. J

    Nature vs Nurture: Exploring the Complexity of Human Development

    does nature or nurture shape us? isn't it just both?
  36. K

    Calculating Complexity of a Problem-Calculation

    I have been given an assignment, a small one, which simply takes in number of points in cartesian coordinate format: (x, y) - then - the assignment specified that the program needed to calculate distances of every permutation possible - then return with the set(s) of points that had the shortest...
  37. Y

    Complexity Concept in Statistical Mech.

    i am ineterested in complexity concept do u know any introductory documan on net ...
  38. G

    More space complexity: Savitch's Theorem

    On Sipser page 279: If a branch of an NTM uses f(n) space, we know that f(n) is the maximum number of (input) tape cells that it scans on any branch of its computation for an input of length n. But we don't know how many times it runs back and forth over those cells before the computation...
  39. G

    Solving Space Complexity of Sipser's NFA Algorithm

    From Sipser's "Introduction to the Theory of Computation", pp. 278-279 I don't see why the maximum length of an accepted string is 2^q. I believe that 2^q is the number of possible combinations of marked states, since there are |q| states and each one can either be marked or unmarked. But...
  40. G

    What happens to the coefficient in O(t(n)b^{t(n)})?

    In Sipser, "Introduction to the Theory of Computation", a proof that "every t(n) time nondeterministic single-tape Turing machine (where t(n) ≥ n) has an equivalent 2O(t(n)) time deterministic single-tape Turing machine" shows that the running time of the equivalent NTM is O(t(n)b^{t(n)}) and...
  41. wolram

    Exploring the Complexity of String Theory

    Its an open question, To my little brain LQG is the only contender, even though it is still an ongoing work. I have read lots about ST, but as someone pointed out, you can not understand it without understanding the maths, but why is it so complex? Surly beautiful theories are easy to...
  42. R

    Measuring Complexity in Biological Systems

    The term "complexity" is currently used in the study of non-linear dynamics. The main problem with this term arises when is applied to biological systems. For example, does evolution generate ever more complex organisms? A good measure of complexity is lacking. We can observe complexity at...
  43. E

    Is the value of n_0 in complexity questions precise or flexible?

    Let's say f(n) = O(g(n)), i.e. f(n) < cg(n) for some n > n_0. Does the n_0 have to be a precise point of intersection of cg(n) and f(n) or just any point for which n > n_0? Thanks in advance.
  44. E

    Calculating Time Complexity for Algorithms: Understanding and Solving Problems

    Hello, I am trying to understand how to solve problems relating to time complexity of algorithms, esp. problems of the following kind: An algorithm takes 0.5 ms for input size 100. How long will it take for input size 500 if the running time is the following: linear, nlogn, n^2, N^3 An...
  45. G

    Where threads abt chaos & complexity?

    Hello, I don't see any specific forum about chaos, self-organised complexity, emergence etc Are there any particular reasons why? How is currently the status / reputation of these fields among scientists? Time ago I read that they couldn't yet deploy any actual theorems in the mathematical...
  46. A

    Exploring the Complexity of String Theory Equations

    Hello people, I've been wondering a lot what the string theory equations look like. I have asked this question a while ago and no one answered, so I am guessing its a hard question. But if anyone could answer I woudl be greatfull..thanks. :smile: :smile:
  47. O

    Constructing and Exploring Non-Trivial Numerical Complex Models

    Let us say that we wish to construct and explore a non-trivial numerical form of structural/dynamic abstract or non-abstract complex models. If there was a way to choose the unique building blocks that we need for this goal, it was our gate to the universe of complexity exploration. For...
  48. M

    From Complexity to Simplicityand back?

    (Humm where the heck does this thread belong??) Heck proving that "Simplicity breeds Complexity" is about the simplest of things, here, on the net, as all of what you are reading/viewing is simply a collection, a stream, of "ones and zeros" current/no-current (electrical current) and yet its...
Back
Top