# What is Complexity: Definition and 147 Discussions

Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, meaning there is no reasonable higher instruction to define the various possible interactions.The term is generally used to characterize something with many parts where those parts interact with each other in multiple ways, culminating in a higher order of emergence greater than the sum of its parts. The study of these complex linkages at various scales is the main goal of complex systems theory.
Science as of 2010 takes a number of approaches to characterizing complexity; Zayed et al.
reflect many of these. Neil Johnson states that "even among scientists, there is no unique definition of complexity – and the scientific notion has traditionally been conveyed using particular examples..." Ultimately Johnson adopts the definition of "complexity science" as "the study of the phenomena which emerge from a collection of interacting objects".

View More On Wikipedia.org
1. ### Comp Sci Solving Complexity Issues: Merging Algorithms

So I have this problem to solve, I was thinking that for k=2, the threshold value is too low and inefficient, but I'm not sure when k is at logn or more. If 2 sorting algorithms have the same complexity, won’t merging them be pointless in terms of running time? For b), i think the merged...
2. ### MHB Time complexity of Breadth First Search, why and how?

Firstly, how is time complexity of BFS $O(b^d)$. Say I have this tree with goal n, how do I calculate time complexity for it? Assume left to right traversal. I know the answer is a,b,c,x1,d,e,f,i,j,k,g,h,z,l,m,n. But I am not sure how to calculate time complexity here using the above formula
3. ### Comp Sci Complexity for generating strings of length k from CNF grammar

Here's the following code I've written for generating strings of length k given a CNF grammar ( Chomsky Normal Form grammar ) ( The code is a recursive variant of the CYK algorithm ). The algorithm is recursive and uses memoization. def generate_language(rule_dict, start_var, k): mem =...
4. ### A Compactness and complexity in electrodynamics

As human beings, we tend to act and observe and think over time periods spanning a few milliseconds to several decades (or even centuries.) Essentially all phenomena that we directly engage with in everyday life are electrodynamical (with quantum electrodynamics over reasonably short time and...
5. ### Calculate complexity of the game of life (cellular automata)

I want to calculate the kolmogorov complexity of n evolution of a game of game of life(game of life is a kind of cellular automata). I’m not searching for the complexity of a certain pattern of cells but for the total complexity of an initial set of cells over n evolutions. Does it make sense to...
6. ### Python Complexity of the Steganography Encryption Method

I have implemented steganography encryption and decryption process, and I wondered if someone could decrypt the message in these conditions; (a) without having the original image (b) having the original image. The encryption starts from the first color code and the first pixel. (c) having the...
7. ### Evaluate the complexity of this graph coloring algorithm

Hello everybody, I should evaluate the complexity of this graph coloring algorithm. To do this, I use the adjacency matrix in which the graph nodes are the elements on the diagonal, while the elements outside the diagonal indicate if a node is adjacent to another ##(A_{i,j} = 1)## or not...
8. ### I Is Complexity in Mathematics Determinate?

When the proof justifies the theorem, by a growing alphabet, then is it possible to talk about the complexity of the theorem via the growing alphabet of the theorems proof? In as short as possible, would it be possible to entertain the notion that complexity in non-congruent mathematics is...
9. ### I Integer Complexity: Exploring an Interesting Notion

Not a question as such, but an interesting notion that I came upon (maybe some other people would find it interesting too). It seems to have been introduced in 1950's and seems a good amount of work has been done on it. For example: 12=(1+1+1)*(1+1+1+1) So the complexity of 12 is 7 since it can...
10. ### Comp Sci Prove Dijkstra's O(E + VlogV) complexity

My effort: I think that the sorting problem in question is Heap Sort which has an O(logV) complexity, but how can I operate with that information so I can solve this? Can you help me by giving me the outline of an idea?
11. ### I Emergence of Complexity and Life

Life, on first glance, appears to violate the second law of thermodynamics. This is because we see an apparent increase in complexity over time, i.e. a decrease of entropy. The resolution of this apparent violation is supposed to be that the sun provides enough energy and expends enough entropy...
12. ### Request to Improve the Complexity of a Probability Question for students

Hi, I want to frame the above Probability question for computer science students. I have stated my idea above but I want to refine it so that it becomes a more comprehensive real world problem. Zulfi.
13. ### A Hawking Radiation: Understanding Complexity in Black Holes

If we take the perspective that black holes thermalize (reach maximum entropy) in a very short time and then just sit there and grow in complexity, how do we interpret Hawking radiation in this picture? i.e. you can't just have the state of the black hole keep growing in complexity forever...
14. ### Interesting Path to Eukaryotic Cell Complexity Proposed

The Inside-Out hypothesis, proposed in this paper (open access), explains the origin of several eukaryotic cellular structure based upon the cell geometry resulting from expansions cell protrusions becoming the cell's non-nuclear cytoplasm. Here is their summary diagram: and their caption...
15. ### Comp Sci Time Complexity Algorithm Proof

Use the formal definition of Big-Oh to prove that if f (n) and g(n) are nonnegative functions such that f (n) = O(g(n)), f (n) + g(n) = Ω(g(n)). By the definition of Big-Oh: If f(n) and g(n) are non-negative functions such that f(n) = O(g(n)) there must be positive constants c and n0 such...
16. ### Complexity of this heap algorithm

I'm trying to count running time of build heap in heap sort algorithm BUILD-HEAP(A) heapsize := size(A); for i := floor(heapsize/2) downto 1 do HEAPIFY(A, i); end for END The basic idea behind why the time is linear is due to the fact that the time complexity...
17. ### I don't understand my prof's notes relating to time complexity

Problem Statement: I've attached a picture of his notes. For a sorted array, to update it he put: O(logn)+O(1) Relevant Equations: O(n) + O(logn) = O(n) I don't see how it can be O(logn)+O(1) and not O(logn)+O(n) in the worst case After you find the index that needs updating, and you...
18. ### Time complexity for an OS to find a file/directory?

What is the time complexity for an OS to find a file? Is it O(1) time? Let's say for example, you had a billion files in a single folder, and you wanted to load a file into a string in your program, would the system find a specific file right away, or would there be a longer wait? Let's...
19. ### Time complexity of a binary search

Binary search works by eliminating half of the objects in a sorted array every time,so shouldn’t it’s time complexity being ##O(\log_2 n)## instead of ##O(\log n)##?
20. ### I Would complexity re-emerge if cosmic expansion reversed?

Imagine that for some reason the current slow expansion of the universe is going to reverse, and the universe is going to collapse back to the pre-inflation state. [Let's make this an assumption without worrying about the mechnism] So we have a very dilute and cold distribution of energy, since...
21. ### Other College Physics: Struggling with Time & Complexity

I am in my 4th year (3 semesters left including the current one), taking mechanics, E&M, quantum mechanics, and a lab course. For each of the three main courses, we get one problem set per week that's around 5-8 questions. In addition to that there's a lab report due every 1-2 weeks. It really...
22. ### I Is fine tuning maximized complexity?

It is often argued that the constants of nature are so finely tuned for life, that the slightest change to them would disallow life. Is this the same as saying that they are what is required to maximize complexity in the world?
23. ### Calculations prior to determining algorithm complexity order

Hello to everyone who's reading this. The problem that I'm struggling with, and it's solution, are typed below.: Homework Statement PROBLEM STATEMENT: Assume an array [0, ... n - 1] of int, and assume the following code segment: for (int i = 0; i < n - 1; i++) if(a[i] > a[i+1])...
24. ### The order of complexity of the Pascal code -- like n * log(n)....

Homework Statement The kind of problems i we are currently dealing with in school are like this: Find the order of complexity of the function Homework Equations 3. The Attempt at a Solution [/B] Im suppose to guess or calculate the complexity of this based on code sample. Its in Pascal and...
25. ### Java Help-Improving runtime complexity of the method

Hello everyone, Looking for a more efficient solution to method 'what', in terms of run-time complexity and space. The method finds the largest cell sequence that the organs sum is divided by 3.(Correct me if I'm wrong) As it seems runtime complexity here is O(n ^ 3). I came to solution of O(n ^...
26. ### I What "language" means in Kolmogorov complexity?

Please help me to understand the answer I found on mathoverflow. The question was: "Do all uncountable sets contain elements with infinite Kolmogorov complexity?" The reasoning is clear for me, but I'd like to understand every word of the answer, which is the following: "...given a language...
27. ### A Viewpoint: Black Holes Produce Complexity Fastest

Yesterday I came across this article about speed limit on the growth of complexity in quantum gravity, that I found interesting: Theoretical results suggest a precise speed limit on the growth of complexity in quantum gravity, set by fundamental laws and saturated by black holes. The article...
28. ### B Exploring the Complexity of 0: Real, Imaginary, or Both?

I was just thinking about this question, and I see 3 possible answers: 1) 0 is a purely real complex number. This seems to be the most intuitive, however the one problem is that it shows up on the imaginary numberline. 2) 0 is not real nor imaginary. I understand this one, but I have found one...
29. ### Why is the complexity class expression this?

I'm trying to understand complexity class algorithms off of my professor's lecture notes, but I still can't get a hang of it. void sort(int a[], int N) { //N is the length of the array for (int base=0; base<N; ++base) for (int check=base+1; check<N; ++check) if...
30. ### Insights The Complexity of Modern Science - Comments

mfb submitted a new PF Insights post The Complexity of Modern Science Continue reading the Original PF Insights Post.
31. ### Graph isomorphism problem-advance in complexity research

There seems to have been a major step forward in complexity research. somebody wrote a pleasant understandable piece about it in Quanta magazine. https://www.quantamagazine.org/20151214-graph-isomorphism-algorithm/ I gave the title an "intermediate" tag because the graph isomorphism problem is...
32. ### How can I learn computational complexity?

Hi all, I was watching a lecture on MIT OpenSource website that is called Algorithmic Lower Bounds: Fun with Hardness Proofs. I am very interested in the content of the lecture, but I couldn't understand most of the information, such as P and some specific terminologies. I tried to look them up...
33. ### Can I use the Master Theorem here? (Algorithm Complexity)

Homework Statement What is the complexity of the following recurrence: T(n) = (9/4)T((2/3)n) + n² Homework Equations My question is: can I use the Master Theorem here? The Attempt at a Solution My attemp: a=9/4 b=3/(1/2) (this is where I think I may be wrong) f(n) = n² so, in this case T(n)...
34. ### Average complexity -- worst case of an algorithm

Homework Statement a Write an algorithm to find the median of three distinct integers a,b,c b Describe D, the set of inputs for your algorithm, in light of the discussion in Section 1.4.3 following Example 1.9. This section discusses Average complexity for an algorithm which involves an...
35. ### Complexity of Go: Calculating the Game Tree Estimate

I have found various Internet sources claiming words to the following effect, regarding the board-game Go: "It is commonly said that no game has ever been played twice. This may be true: On a 19×19 board, there are about 3^361×0.012 = 2.1×10^170 possible positions, most of which are the end...
36. ### Structures: dynamic, complexity, organisation

Hi, I have to make a project for school about the topic on the title. It must be a personal work, i mean i can't choose a difficult subject cause then all my presentation could be just a simple documentation. Also, the project could include just one or two of the topics in the title. I thought...
37. ### Quantifying the complexity of a system

Are there generally accepted methods for quantifying the complexity of a system, enabling comparison and the requirements for quantitatively modeling it? Think everyone would agree that in complexity, for example a double pendulum is less complex than the global climate which is in turn less...
38. ### Black Hole Quantum Complexity

Leonard Susskind talks about Black hole Quantum Complexity in one of his online lectures. I was wondering what you guys on the forums think about this, and what you guys think it means. Here's a link to the video He points out that the complexity increases linearly with time, and at the...
39. ### Algebra Seeking the Recommendation on Complexity Theory

Dear Physics Forum personnel, I am a rising college junior in US with a major in mathematics and an aspiring applied mathematician in the fields of theoretical computing. I just recently got a research project on the complexity theory about the algebraic computation, approximation, and measure...
40. ### MHB Differential equations - Decidability and Complexity

Hey! :o Is someone familiar with the following? We have linear differential equations with polynomial coefficients depending on x. $a_n(x)y^{(n)}+ \dots a_1(x)y^{(1)}+a_0(x)y^{(0)}=b(x)$ There are problems like if there are solutions, if the solutions are linear independent and so on and...
41. ### Delay complexity of Boolean functions

Homework Statement I don't really understand how/why every Boolean function of n variables may be implemented with a delay complexity of O(n). Could someone please try and explain? Homework EquationsThe Attempt at a Solution I was trying to show it using minterms (SOP). There is a maximum of...
42. ### Complexity Analysis problem of an Algorithm.

##A,B## are symmetric matrices of graphs ##G,H## respectively. For ##x \in G##,consider the graph ##(G-x)##, it has vertices adjacent to ##x## and vertices non adjacent to ##x##.## A_x## is the symmetric matrix of the graph ##(G-x)##, where ##C## is the symmetric matrix of the graph created by...
43. ### MHB How can the time complexity be achieved?

Hello! (Wave) It is given as input an undirected graph $G=(V,E)$, weights of edges $w_e$ and a subset $U$ of the vertices. The output should be the minimum spanning tree at which the vertices of the set $U$ are leaves. (The tree could also have leaves from the nodes of the set $V-U$). I...
44. ### Help with Kolmogorov Complexity proof

Hey, has anyone here done Kolmogorov complexity? I hadn't, and I was just reading the Wikipedia page to start learning it. The core concept makes sense: The Kolmogorov complexity for a a string s, K(s) is equivalent to the length of a program that generates that string (It can be any math...
45. ### MHB Complexity of Union Algorithm

Hello! We have a directed graph G=(V,E) ,at which each edge (u, v) \in E has a relative value r(u, v) \in R and 0 \leq r(u, v) \leq 1, that repsesents the reliability , at a communication channel, from the vertex u to the vertex v. Consider as r(u, v) the probability that the chanel from u to...
46. ### MHB What is the Time Complexity of this Vertex Cover Algorithm?

Hello! (Wave) I want to write an algorithm that finds an optimal vertex cover of a tree in linear time $O(n)$, where $n$ is the number of the vertices of the tree.. A vertex cover of a graph $G=(V,E)$ is a subset $W$ of $V$ such that for every edge $(a,b)$ in $E$, a is in $W$ or $b$ is in...
47. ### MHB What is the Time Complexity of These Binary Search Tree Functions?

Hello! (Wave) The following two functions are given and I want to find their time complexity. function BinarySearchTreeLookUp(key K,pointer R): Type if (R==NULL) return nill; else if (K==R->key) return R->data; else if (K<R->key) return(BinarySearchTreeLookUp(K,R->LC))...
48. ### Dirac Equation computational complexity

How fast does the computational complexity of the Dirac equation, with regards to full* solution, grow with number of particles N? can we specify the order of time t(N) for this solution in terms of t(N=1)? (I assume that number of protons, neutrons and electrons combined is N - i.e. that...
49. ### MHB Exploring the Complexity of Satisfiable Boolean Expressions

Hey! :o The Boolean expression $(p_1+p_2)*p_3$ can be represented by the string $(1+2)3$, where integer $i$ represents variable $p_i$. Consider the language $L$ consisting of all strings representing satisiable Boolean expressions (those for which some assignment of $0$'s and $1$;1 to the...
50. ### MHB Constructing a Star System with O(1) Complexity

Hey! :o I want to write a function for the constitution of a star system "ss". The new star system contains an empty list of planetary system, that means that in the list of the planetary system exists only the sentinel node, and the empty tree of the free-floating planets (ffp). The new star...