@evinda that there exist algorithms of towerian or higher runtime?

wouldn't a 334 k6 5-regular grapth + k10 5-regular graph make 2014 5-regular graph ?

@Ali.B what do you mean by a $K_{10}$ 5-regular graph?

@JMoravitz You you mean that there are problems that belong to NP but are solved in a worse time than exponential time? I thought this would be the worst case

$K_{10}$ is not 5-regular, it is 9-regular

sorry I meant something like this

@evinda en.wikipedia.org/wiki/Time_hierarchy_theorem

There are nonexponential time algorithms. With enough googlesearching you could find one,

@Ali.B That graph is called $K_{5,5}$, the complete bipartite graph on 10 vertices with equally sized partitions

and yes, that would be sufficient to prove the statement.

ok thanks alot for your time @JMoravitz

Since the question did not specify that the graph needed to be connected, you may use multiple components like that

:)

@Ali.B I still find the induction argument more compelling, since your argument only shows that you can construct 5-regular graphs on $a\cdot 6 + b\cdot 10$ vertices with $a,b\in\mathbb{N}$

using $a+b$ components

yeah, but I find it too complicated for the question because it only asks to build it, and asks for proof only if you can't build it.

This makes me curious now, if there exists a simple 5-regular graph on 7 vertices. If there is, then we can prove that there exist 5-regular graphs of any size

the answer to that question quickly verified as a no. cough. Proof: apply the handshaking lemma.

exponential time is not the worst case however @evinda

there are worse-cases

A great day here, full of tutoring and fruitful research. I'd like each day be like that.

How could we apply the handshaking lemma to prove it? @JMoravitz

@robjohn did you ever try this one? $$\int_0^{\pi/2} \arccos\left(\frac{\cos(x)}{1+2\cos(x)}\right) \ dx$$

oh, @evinda I was referring to handshaking lemma to prove there doesn't exist a graph on 7 vertices that is 5-regular

@JMoravitz I haven't got taught the towerian function... :/

What else could I say? @JMoravitz

hi @JMoravitz, @evinda

Hello @TedShifrin :)

Hello @TedShifrin!! Are you familiar with characteristic curves??

@evinda double-exponential time algorithms are a subset of towerian algorithms, and not a subset of exponentialtime algorithms., I.e., an algorithm is double-exponential if it is $O(a^{b^n})$

Haven't thought about them in 20 years, @MaryStar.

e.g. $2^{(2^n)}$

Hi @TedShifrin

hi mr eyeglasses

@evinda en.wikipedia.org/wiki/2-EXPTIME

hello @TedShifrin, Bună ziua @Chris'ssis

@JMoravitz So do I have to refer to these functions?

Ok... Could you though take a look at math.stackexchange.com/questions/1202693/characteristic-curves ?? Do you have maybe an idea?? @TedShifrin

salut, @Gato

@evinda www2.informatik.uni-freiburg.de/~ki/papers/Rintanen03compl.pdf here is a paper that seems to prove that its algorithm runs in 2-exp time

Salut :-) Ce mai faci, maestre? ;)

@JMoravitz But we haven't talked about it in class...

@Chris'ssis No, I don't think I did...

Sunt bine, și tu? @Chris'ssis

@Ted perhaps you can give a reason to @evinda why there exists an algorithm with runtime of any desired function (double exponential or higher)

I'm floundering at the moment to provide an elementary example

In Romanian is it ' blabla ?' or 'blabla?' for the '?' @Chris'ssis

@Gato Excelent, mi-s in mare forma astazi! :-)

Hello.

@Gato A kind of talking for the sake of talking, sometimes with not much sense, or it has the sense you say somehting stupid.

@Chris'ssis Pentru că ai rezolvat 'integrale' (not sure for this word) ?

O_o

@TedShifrin What's up ?

@Gato o/

@Gato integrale=integrals

@Hippalectryon Comment vas tu ?

@Gato Ca va et toi ?

@Chris'ssis I am asking for the place of the '?' in the sentence, in french we introduce a space between the word and the '?', not in englis. Ok integrals, thanks.

The simplest example I can come up with @evinda of an algorithm that runs in arbitrary $f(n)$ time is very simply is to "repeat this process $f(n)$ times." For example, The input is $n$ and the output is $f(n)$ through the process of repeating $1+previous=new$ a total of $f(n)$ number of times.

@Hippalectryon ça va, tu as fait calcul diff ?

@Gato un peu

Is that a particularly useful algorithm? no, but it is an algorithm all the same.

@JMoravitz So is this an algorithm in NP?

@evinda But, it does give an example of an algorithm which runs in $f(n)$ time. What remains to be proven is that there exists an $f(n)$ which grows faster than any exponential-time algorithm

@Hippalectryon Un peu c'est à dire : un peu mais je maitrise ce peu ou on a un fait ça un peu mais bofbof en terme de connaissance sur le sujet ? :p

@Gato It's like: Ce mai faci? (no space between)

@Chris'ssis thanks, good to know :)

@Gato ;)

@JMoravitz How can we find an algorithm that is in NP?

Yes, @evinda You have P (polynomial time) and NP (nonpolynomial time), but you can further partition NP into EXP and NEXP

@Gato Le programme a été considérablement réduit avec la réforme des prépas

and you can partition further if you like

@JMoravitz I thought that NP does NOT stand for "non-polynomial time" but for NONDETERMINISTIC polynomial time...

The example I described at the beginning of the conversation was that $P\subsetneq EXP\subsetneq TOWERIAN\subsetneq WOWZER\subsetneq ACKERMANIC$

@Hippalectryon c'est vrai, j'avais oublié. :)

@JMoravitz Ok, but we haven't said something like that in class... So is it the only way to answer the question?

@Hippalectryon Un médaillé fields sera à lille 1 dans une semaine. Martin Hairer

@Gato :O j'ai qqn qui sera à Lille dans une semaine, je vais lui dire

@Hippalectryon Oui, un colloq en anglais pour les chercheurs mais je vais y aller quand même

@evinda hmm, I'm looking up definitions, my current understanding was that $NP = P^c$, Looking at en.wikipedia.org/wiki/Time_hierarchy_theorem#Consequences it appears that my interpretation is incorrect, as it says $NP\subsetneq NEXP$

@Gato Il faut une invitation/autorisation ou .. ?

@Hippalectryon Non, sinon je ne pourrais pas y aller..

@evinda according to this definition here: en.wikipedia.org/wiki/NP_%28complexity%29 you have $NP = \bigcup_{k\in\mathbb{N}} NTIME(n^k)$

Donc c'est totalement ouvert ? Ca se passe où à Lille?

@Hippalectryon univ-lille1.fr/Accueil/evenements/?id=46064

@Hippa!

@BalarkaSen!

@Ted!

which would imply that my answer all along is incorrect, that $NP$ problems can be solved in exponential time (yet I still remind you that there exist things worse than exponential time, but according to these definitions are in a class higher than $NP$)

My test is tonight. :/

@Owatch In which subject?

hi @Hippa, @Balarka.

Calc2

@Gato Merci

@JMoravitz So do we have to say something about the fact that they can also be solved in a better time as in exponential time?

@evinda Owatch has been hanging out in the chatroom a good bit lately asking for integration tips/tricks.

@Owatch Good luck

@JMoravitz Aha!

@TedShifrin Mayer-Vietoris is quite some powerful tool.

Ayup @Balarka.

It is in fact easier than the closely related Van Kampen theorem. You don't need to compute the maps from the intersection, for one. And you don't need any path-connectivity condition either.

@Balarka: The freshmen in my multivariable math class were shocked to find out there could be a $k$-dimensional compact manifold in Euclidean space that was not a boundary of a $k+1$-dimensional manifold with boundary.

Well, you often do need to compute the maps from the intersection.

@TedShifrin Well, boundaries of manifolds are always closed.

Yes, so?

And there are non-closed manifolds.

But I started with a compact one :P

@Balarka: He meant closed manifold. Don't pick at technicalities.

Morning, by the way.

good night, @Mike

when I say compact manifold, I mean no boundary ... One must say manifold with boundary if there is to be a boundary.

@TedShifrin complex analysis, do you like ?

that would get annoying when one frequently wants to consider manifolds with boundary, eg when one's main interest is (closed!) 3-manifolds

@Gato, very much. My field was complex differential geometry.

@MikeMiller ah, I didn't note the word "compact".

Well, @Mike, in advanced situations, you're welcome to make any convention you want.

but of course such a thing is not the goal for your multi variable class. :P

For example, @Mike, in my undergraduate diff geo class, every surface is connected.

Otherwise, all sorts of results must be phrased in the form of "every component is ..."

Where is advisor Tee dog?

well, but surely every n-dimensional closed manifold can be realized as a boundary of an (n+1)-dimensional manifold?

Surely not, @Balarka.

just cross it with [0, 1)!!

What?

Now you've done it, @Balarka. Mike's putting you on ignore again.

X be an n-dimensional manifold. Consider $X \times [0, 1)$.

You were so into bordism a month ago. Did you forget everything you spent time thinking about?

Ah.

In that case, what was the point?

OK, fine, compact manifold with boundary. I got tired of typing compact.

lol

I'm bored with bordism, @Mike.

compact. right. in that case, consider a point.

:P

i'm so slow.

My analysis professor was introducing spaces of functions today, and I have in my notes that if $K$ is any compact set, then the complement of $K$ is the set of all continuous functions $f: K \to \mathbb{R}$ and this doesn't make sense to me..did I copy down the notes correctly?

Now come up with an interesting example...

Let's do it with $k>0$, @Balarka.

No, mr eyeglasses

all you told me is that $\Omega^0$ is nontrivial, which is about as interesting as the fact that $H^0(pt)$ is nontrivial

Not complement. The space he's considering is $C(K,\Bbb R)$, the space of continuous maps.

@TedShifrin What do I need to correct

@TedShifrin Great :D. I would like to prove that for a holomorphic function we cannot have $f(\frac{1}{n})=\frac{1}{2^n}$. First I prove that $f(0)=0$ and $f'(0)=0$, so my idea is to prove that there are infinity zero, so as $f$ is holomorphic then is analytic on open disk. Then I worked by induction, assuming that $f(0)^{(j)}=0$ for any $j=0,..,k-1$. After that I wrote $f(z)=\sum_{n=k}^{+\infty}a_n z^n$ and now I used the fact that $a_k=\frac{f^{(k)}}{k!}$. Does the reasoning is correct ?

Suppose we have functions g:M -> G and h:M ->G where M is a smooth manifold and G is a Lie group. I'm trying to prove a version of the product rule for Lie groups.

That is, I want to show for p in M, d(gh)_p = (L_g(p))_* dh_p + (R_h(p))_* dh_p. L_(g(p)) takes a group element and multiplies g(p) on the left, so I am composing its pushforward with the differential of h at p. Similar for the other term. What's the best way to do this? Maybe use the version of the differential in terms of the derivative of a curve?

I haven't really given bordism much thought, @Mike. But school's off tomorrow, so I'd be glad to. Let me think.

Also, good afternoon everyone

$\int \frac{x^2+1}{(x-3)(x-2)(x-2)} dx$

Is this ready for putting it in partial fractions?

So you're trying to show all derivatives vanish at $0$, @Gato?

@TedShifrin $C(K, \mathbb{R})$ is the symbol for the space of all continuous functions $f: K \to \mathbb{R}$?

@TedShifrin yes.

yes, mr eyeglasses ... and there's a norm and/or metric on that space.

How about $[0, 1]$?

@Balarka: You're starting with a compact manifold without boundary.

@TedShifrin I think he was having a bad day..he almost never makes any errors, but this particular lecture he made a ton

OK, OK. I'm forgetting all these conditions.

@Balarka: When you're old like me, you get to forget so much.

So everything is a circle and disjoint union of circles.

dimension 1 is not so interesting, @Balarka.

But then you can always realize a circle as boundary of a disk.

Ah okay, he defined the metric $d(f,g)$ to be $\max \{|f(x) - g(x)| \mid x \in K\}$

@Ted: I understand your frustration from me forgetting things I ask you about...

So dimension 1 doesn't give us a counterexample.

There you go, mr eyeglasses

Everything else makes sense then

@gato: I don't know how much complex analysis you know. Do you know more about the local nature of an analytic function?

@teadawg1337 If you're available to help me with a partial fraction or two that would be great! If you're busy it's cool.

@Mike: We applied Stokes's theorem to a torus in $\Bbb R^4$ today :P

Sorry ... was wiping off the keyboard. smacks mr eyeglasses

lol

We were actually communicating in secret code

hello,

OK, I have a huge pile of diff geo homeworks to grade. Bubye for now.

Later @TedShifrin

@TedShifrin I did the open mapping theorem, maximum principle, zero isolated, analytic function : Liouville's theorem, fundamental theorem of algebra.

Well, I guess I need to take something nonorientable.

Oh, @Gato, then you should know that locally an analytic function looks like $z^n g(z)$ for some $n$ and some analytic function $g$ with $g(0)\ne 0$. That will do it.

@TedShifrin Yes I have this, I forgot. Too much theorem, thanks.

Hi I have a question.

Suppose I remove 10 terms from a Fourier series

Will the new series remain a Fourier series?

By "remove" I mean I make the fourier coefficients 0 for any 10 fourier coefficients of my choice

You don't need to in general, @Balarka. You do in dimension 2.

I am thinking about dimension 2.

You probably don't have the tools to prove the existence of a counterexample.

I am pretty sure something nonorientable is needed since otherwise we have a well defined notion of "inside" and we can "fill" that "inside" to get the desired 3-manifold.

You should use actual math words. The only reason I can interpret that is because I already know what you're doing.

@TedShifrin hey Ted!

Not asking you to edit what you wrote, just saying that it's going to be real hard to interpret you when I don't know what you mean in advance...

To anyone who was thinking about my question, never mind. I figured it out

@MikeMiller Can't. I only have an intuitive idea of orientability. The best I can do is : if $M$ is an orientable manifold then after embedding $M$ inside $\Bbb R^n$, $M$ bounds a closed subset of $\Bbb R^n$. This is the $3$-manifold we want.

You know what the orientable 2-manifolds are.

Oh, of course. Hehe.

$\int \frac{x^{2}+1}{(x-3)(x-2)^{2}}dx$ was put into the form $x^{2}+1 = A(x-2)^{2}+(Bx+C)(x-3)$

Does this seem correct?

They're just genus $g$ surfaces -- but they're all boundaries of solid genus $g$ surfaces.

You know (because you know what the orientable 2-manifolds are) that they support an embedding into $\Bbb R^3$ which separates the plane into two components; the closure of the bounded component is the desired 3-manifold. You can't just state that an embedding of a surface splits $\Bbb R^3$ into two components; this is false without further conditions. You also can't state that an orientable n-manifold embeds into $\Bbb R^{n+1}$. That's not true in general.

Fair enough. I haven't thought about these kinds of things, sorry if I am being slow.

@Owatch, you want $\frac A{x-3} + \frac B{x-2} + \frac C{(x-2)^2}$

Why?

You have x-2 twice? One time it is squared?

because you have $(x-2)^2$

Yeah, so why not use Bx+C?

the point is to be able to integrate. is easier to integrate $\frac 1{{x-2)^2}$ and $\frac 1{x-2}$ than $\frac{Bx + C}{(x-2)^2}$

Change one bracket to parentheses next to X

i dont have mathjax installed. i cant really see how it is rendering.

But how can you write ...$+\frac{C}{(X-2)^{2}}$?

@abel Use a web service or something to see what I output then

If it's squared, and you only have C on top?

I thought anything that would have x^2 would require Bx+C

@abel hi, this will enable mathjax in your chat.

you can split $\frac{Bx + C}{(x-2)^} = \frac{B}{x-2} + \frac{C+2}{(x-2)^2}$

guys i dont know how to do that now. i will check into that later. just bear with me.

Okay.

I don't understand how, but I will do it that way.

Oh I see.

Could someone help me at thefollowing??

you will see better why we do tthat when you try to find $\int \frac{x^2 + 1}{(x-3)(x-2)^2}$

@Mary can you explain how you did that?

I just cant figure it out

What do you mean?? @G-man

What do you mean?? @G-man

How I found the characteristic curves?? @G-man

What do you mean?? @G-man

How I found the characteristic curves?? @G-man

I mean how'd you make the question appear here in chat. I seem to be the only one who doesn't know how to do that.

And no need to repost.

copy the link of the post and paste it here without writing anything and send it... @G-man

$\int{\frac{1}{(x-2)^{2}}}dx$

(accedentaly I send it more times, sorry)

I can make a single U Substitution to change it to $\int{\frac{1}{u^{2}}}du$

beats the hell out of himself for being so stupid

But now what.

I cannot substitute u^2 for t, that will require differentiating u^2 and getting 2u in the integral, which will not work.

I don't really think you need any subs.

Oh

I can make it u^-2

$\int \frac{dx}{(ax+b)^2} = -\frac 1a \frac{1}{ax + b}$

Just integrate it normally, just as you would for $1/x^2$. That's the thing with linear expressions. You just divide by the coefficient of x in the end.

moral is $ax + b$ is as good as having plian $x.$

:/ I got it wrong.

This is frustrating. I don't have that much time. I need to practise many problems. Wasting hour on one single IBPF problem.

Hello @abel !! Could you take a look at math.stackexchange.com/questions/1202693/characteristic-curves and tell me if it is correct??

Whatever, I'll redo it yet again.

@abel How is this easier? Now x^2 + 1 = A(x-2)(x-2)^2

So I have to do a cubic?

o_o

@MaryStar, i am not sure what is it you need to do.

I am getting two numbers for a single variable. . .

I will do as you said Abel.

I give up.

I cannot solve it

@MaryStar, if you can clearly specify, you can make the edit on the main site, i will take a look at it this evening.

why don't you try for some concrete $f(x,t)$ to check your method? one way is to pick a known $u$ and adjust $f$ to fit that $u.$

@Owatch $x^2+1=A(x-2)^2+B(x-3)(x-2)+C(x-3)$ should be the equation you're working with to simplify the integrand in that problem

What do you mean?? Could you explain it further to me?? I got stuck right now... @abel

Also, if you think about it, $\frac{B}{x-2}+\frac{C}{(x-2)^2}$ is of the general form $\frac{Bx+C}{(x-2)^2}$

@Owatch You asked for my help, did you not?

Tensor products of modules make me feel like such a $M\otimes_R \circ N$

Everyone here who frequents the review queues and is annoyed about those pesky one-character edit suggestions, please raise your voice.

take $u = xt$ it satisfies the boundary conditions and the required $f$ would be $f = 1.$ now work backwards, given $f = 1,$ can you reproduce $u = xt?$

@teadawg1337 I was in the bathroom.

Im back now. Yes

Do I have to use Green's Theorem to reproduce $u$ ?? @abel