Complexity Definition and 148 Threads

Let ##m## be Lebesgue measure. It is another proposition that the functions ##NBV## are in one-to-one correspondence between complex Borel measures, e.g. ##F\in NBV## induces a complex measure ##\mu_F## such that ##F(x)=\mu_F((-\infty,x])##. Then in Folland's real analysis text, I'll omit the...

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...

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

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 =...

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...

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...

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...

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...

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...

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...

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?

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...

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.

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...

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...

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...

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...

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...

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...

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)##?

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...

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...

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?

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])...

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...

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 ^...

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...

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...

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...

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...

mfb submitted a new PF Insights post The Complexity of Modern Science Continue reading the Original PF Insights Post.

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...

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...

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)...

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...

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...

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...

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...

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...

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...

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...

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...

##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...

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...

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...

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...

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...

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))...

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...

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...